[Python] DFS/BFS : 프로그래머스 LV.2 타겟 넘버

프로그래머스

문제 설명:

n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 한다. 
사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하라.

ex) numbers = [ 4,1,2,1 ] target = 4 일 경우 아래와 같이 4를 만들기 위해 총 2가지 방법이 있으므로, 2를 return 한다.

+4+1-2+1 = 4
+4-1+2-1 = 4

문제 해설:

BFS / DFS 는  그래프 전체를 탐색하는 방법에 속하는 알고리즘이다. 
• BFS는 너비 우선 탐색이라고 불리며 시작 노드에서 인접한 노드부터 탐색하는 알고리즘이고,
• DFS는 깊이 우선 탐색이라고 불리며 한 노드를 시작으로 다음 분기로 넘어가기 전에 해당하는 분기를 완전히 탐색하는 알고리즘이다.

위의 두 알고리즘을 이해하기 위해서는 자료구조 중 그래프 자료구조와 스택/큐 자료구조의 이해가 선행되어야 한다.

그래프 자료구조는 노드와 간선으로 이루어지고, 간선으로 연결되어 있는 인접한 노드들을 방문하여 확인하는 것을 그래프 탐색이라고 한다.

여기서 스택과 큐 자료구조의 개념을 적용해보면 아래의 그림과 같이 설명할 수있다. 

먼저 스택의 개념이 적용된 깊이 우선 탐색 DFS이다.

이렇게 그래프 자료구조가 있을때, 노드 1부터 시작하여 인접한 노드를 방문 할 것이다.

스택 공간에 노드 1을 삽입하고 방문 처리한다.

노드 1은 방문처리 되었고, 노드 2를 기준으로 인접한 노드 8을 방문하고 스택에 추가한다.

노드 2는 방문 처리 되었고 노드 8을 기준으로 인접한 노드 6 과 7중 숫자가 낮은 6을 방문한다. 이런식으로 계속 스택에 쌓아가면서 최상단 노드까지 방문하고 더 이상 방문할 노드가 없다면 스택에서 하나씩 꺼내어진다. 따라서 아래와 같은 스택 삽입 순서가 결정된다.

1 -> 2 -> 8 -> 6 -> 7 -> 3 -> 4 -> 5, 이와 같이 하나의 브랜치를 아주 그냥 끝까지 갔다가 오는 것을 깊이 판다 하여 깊이 우선 탐색이라 한다.

반대로 BFS 넓이 우선 탐색은 큐를 이용하게 되는데. 그림으로 설명하자면... 아래와 같다.

큐에 시작노드인 1을 넣고 근접한 노드 2와 3을 큐에 넣는다.

방문한 노드인 1을 큐에서 꺼내고, 2부터 방문을 하여 인접한 노드를 본다.

2와 인접한 노드인 8이 큐에 삽입된다. 다음으로 3을 꺼내고 3하고 인접한 노드 4, 5 를 큐에 삽입한다.

노드 8을 꺼내고 인접한 노드 6, 7 을 큐에 삽입한다. 이와같은 패턴을 계속 반복하면, 1 -> 2 -> 3 -> 8 -> 4 -> 5 -> 6 -> 7 순서로 삽입된다.

이제 정말로 문제를 풀어보자. 나는 여기서 스택을 활용한 DFS 깊이 우선 탐색 알고리즘으로 풀어 보았다. 

root_node 말 그대로 루트를 0부터 시작해 numbers에 있는 값을 +,- 하여 자식 노드들을 생성 후 그것을 다시 루트 노드로 변환하여 계속하여 스택에 쌓은 후 마지막 결과에서 타켓넘버가 몇개가 있는지 찾는 방법으로 구현했다.

def solution(numbers, target):
    root_node = [0]
    
    for number in numbers:
        child_node = []
        for result in root_node: 
            child_node.append(result + number)
            child_node.append(result - number)
        root_node = child_node
        
    return root_node.count(target)