[프로그래머스] 깊이/너비우선탐색 1. 타겟 넘버

문제

출처: 프로그래머스

 

---

깊이우선탐색(DFS)/ 너비우선탐색(BFS)

DFS

- 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

- 어떤 노드를 방문했었는지 반드시 검사해야함

- 그래프(정점의 수 : N, 간선의 수: E)의 모든 간선을 조회함

   * 인접 리스트로 표현된 그래프 : O(N+E)

   * 인접 행렬로 표현된 그래프 : O(N^2)

 

BFS

- 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법

- 어떤 노드를 방문했었는지 반드시 검사해야함

- 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용함, 선입선출

- DFS와 동일한 시간복잡도이나 평균적으로 DFS보다 조금 빠르다고 함

 

출처: yunyoung1819.tistory.com/86

---

풀이

꽤 오래 고민해도 잘 생각이 안 나 예전에 C++로 풀어뒀던 풀이를 봤다. 어째 갈수록 더 못 하는 것 같다.

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int number;
int targetNumber;
vector<int> staticNumbers;
int count = 0;

void dfs(int index, int sum) {
    if(index == staticNumbers.size()){
        if(sum == targetNumber){
            count++;
        }
        return;
    }
    dfs(index + 1, sum - staticNumbers[index]);
    dfs(index + 1, sum + staticNumbers[index]);
}

int solution(vector<int> numbers, int target) {
    targetNumber = target;
    staticNumbers = numbers;
    dfs(0, 0);
    return count;
}

그래프처럼 풀려고 했어서 잘 생각이 안 났던 듯 하다. index와 sum을 인자로 넘겨 다음 숫자를 각각 더하고 빼서 재귀함수 형태로 풀었다.

---

다른 사람의 코드

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> numbers, int target) {
    int answer = 0;
    int size = 1 << numbers.size();

    for(int i = 1 ; i < size ; i++){
        int temp = 0;
        for(int j = 0 ; j < numbers.size() ; j++)
        {  
            if(i &(1 << j)){
                temp -= numbers[j];
            }
            else temp += numbers[j];
        }
        if(temp == target) answer++;
    }
    return answer;
}

비트 연산으로 푼 다른 분의 코드를 보았다.

 

<< 는 shift 연산으로 왼쪽에 오는 숫자를 오른쪽에 오는 수만큼 비트를 옮긴다.

즉 1 << numbers.size()은 비트로 보면 왼쪽의 숫자인 0000 0001을 0010 0000으로 5칸 옮긴 것으로 size에는 32가 저장되었다.

 

다음 두 번째 포문 안의 조건문 i &(1 << j)를 보자.

&는 비트 AND연산자이다. i가 1, j가 0일 때

0000 0001 & 0000 0001 은 0000 0001이므로 1이 되어 if문에 들어가게 된다.

 

같은 방법으로 연산하면 두번의 포문을 돌면서 모든 경우의 수를 확인하게 된다.

이해하기 쉽게 출력해보았다.

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int solution(vector<int> numbers, int target) {
    int answer = 0;
    int size = 1 << numbers.size();
    cout << size << endl;

    for(int i = 1 ; i < size ; i++){
        int temp = 0;
        cout << "--------------" <<endl;
		for(int j = 0 ; j < numbers.size() ; j++)
        {  
        	cout << int(i &(1 << j)) << endl;
            if(i &(1 << j)){
                temp -= numbers[j];
            }
            else temp += numbers[j];
        }
        if(temp == target) answer++;
    }
    return answer;
}

int main(){
	vector<int> numbers;
	numbers.push_back(1);
	numbers.push_back(1);
	numbers.push_back(1);
	numbers.push_back(1);
	numbers.push_back(1);
	
	solution(numbers, 3);
	return 0;
}

결과

엄청 오래 걸려서 이해했는데 내거보다 느려서 좀 허탈했다. 그치만 신박한 풀이였다...

 

def solution(numbers, target):
    global new_numbers
    new_numbers = numbers
    global total
    total = 0
    global new_target
    new_target = target
    
    dfs(0, 0)
    
    return total

def dfs(index, sum):
    global total
    if index == len(new_numbers):
        if sum == new_target:
            total += 1
        return
    
    dfs(index + 1, sum + new_numbers[index])
    dfs(index + 1, sum - new_numbers[index])
    
    return
    

파이썬으로도 다시 풀었다.

 

출처: m.blog.naver.com/PostView.nhn?blogId=yuyyulee&logNo=221114544260&proxyReferer=https:%2F%2Fwww.google.com%2F

dojang.io/mod/page/view.php?id=174

dojang.io/mod/page/view.php?id=173