DFS, BFS - 타겟넘버

 

https://school.programmers.co.kr/learn/courses/30/lessons/43165

프로그래머스

이 문제는  DFS, BFS를 이용해 풀 수 있다.

주어진 배열의 각 요소들을 더하거나 빼면서 target 값이 되는 경우를 찾으면 되는데,

모든 요소들을 이용(=방문)해야 하기 때문이다. 

 

주어진 numbers 배열이 [4, 1, 2, 1] 이라고 할때, 다음과 같은 트리의 모습을 생각해 볼 수 있다.

각 노드들을 방문하면서 값을 더하고, 맨 마지막 노드의 값까지 더했을 때의 결과가 target과 같은지 비교하면 된다. 

target이 2라고 할 때, numbers가 [4, 1, 2, 1] 라면 결과가 target과 같아지는 경우는 두 개이다. 

 

1층 노드는 0번째 인덱스 요소이고, 차례로 1번째, 2번째, 3번째 인덱스의 요소들이 (음, 양)모든 경우를 이루어 트리를 만들었다. 

마지막 인덱스의 요소까지 방문했을때, 합을 target과 비교하면 되므로 인덱스를 사용하는것이 중요한 포인트이다. 

 

나는 stack을 이용한 DFS로 풀었다.

def sol(numbers, target):
	answer = 0
    stack = [[numbers[0], 0], [-1*numbers[0], 0]]
    n = len(numbers)
    
    # 스택이 비어질 때까지 반복
    while stack:
    	# stack에서 값 v와 인덱스 i 추출
    	v, i = stack.pop()
        # 다음 인덱스 값을 가져오기 위해 i 하나 증가
        i += 1
        
        # i가 n보다 작다면, 아직 마지막 인덱스까지 방문하지 않았다는 뜻
        if i < n:
        	# 현재 값 v와 numbers의 다음 인덱스 값을 더한것과 다음 인덱스 i를 stack에 넣는다.
            stack.append(v + numbers[i], i)
            # 현재 값 v와 numbers의 다음 인덱스 값을 뺀것(다음 인덱스 값에 -를 붙였다는 설정)과 
            # 다음 인덱스 i를 stack에 넣는다.
            stack.append(v - numbers[i], i)
        # i가 n보다 작지 않다면, 마지막 인덱스까지 방문했다는 뜻
        else:
        	# 마지막 인덱스까지 더한 값인 v가 target과 같다면 answer를 1 증가
        	if v == target:
            	answer += 1
	return answer

numbers = [4, 1, 2, 1] 이고

맨 먼저 stack = [[4, 0], [-4,0]] 이 된다.

그리고 pop을 하면 v, i = -4, 0 이 된다.

현재 i는 0으로 n 보다 작으므로, if문 안으로 코드가 진행된다.

stack에는 새로 1번째 인덱스 값이 현재 v=-4 에 더하거나 빼진 두 경우가 들어가게 된다. stack = [[4, 0], [-4+1, 1], [-4-1, 1]]

아직 stack이 차 있는 상태이므로 계속해서 반복한다.

이번에는 v, i = -5, 1 이고 여전히 i는 n보다 작기 때문에 또 다시 if문 안으로 들어가고 stack에는 2번째 인덱스의 경우들이 들어간다.

stack = [[4, 0], [-4+1, 1], [-5+2, 2], [-5-2, 2]]

새로운 v, i = -7, 2이고 아직도 i는 n보다 작다. 

stack = [[4, 0], [-4+1, 1], [-5+2, 2], [-7 + 1, 3], [-7-1, 3]]

이번에는 v, i = -8, 3으로 i가 n보다 작지 않기 때문에 드디어 else문 안으로 들어가게 된다. 

v = -8로 target과 같지 않기 때문에 answer는 업데이트 되지 않는다.

그리고 stack은 비어있지 않기 때문에 또 다시 위와 같은 과정을 반복한다. 

 

이 풀이법은 일단 한번 길을 들면 계속해서 더 깊은 노드를 먼저 방문하기 때문에 DFS라고 할 수 있다. 

 

동일한 코드에서 자료구조만 queue로 바꾸면 BFS 풀이법이 된다. 

from collections import deque
# 파이썬에서 queue를 쓰려면 deque을 사용하는 것이 좋다.

def sol(numbers, target):
	answer = 0
    queue = deque()
    queue.append([numbers[0], 0])
    queue.append(-1*[numbers[0], 0])
    n = len(numbers)
    
    while queue:
    	v, i = queue.popleft()
        i += 1

        if i < n:
            queue.append([v + numbers[i], i])
            queue.append([v - numbers[i], i])
        else:
        	if v == target:
            	answer += 1
	return answer

동일하게 최초의 queue = deque([[4, 0], [-4, 0]]) 이고, popleft()로 맨 앞의 요소를 먼저 꺼내오면 v, i = 4, 0 이다.

그 다음 과정은 stack을 사용했을때와 동일한데 queue를 사용했을때 BFS인 이유는, 다음 차례에 더 깊은 노드를 방문하는 것이 아니라, 옆 노드(-4)를 방문하기 때문이다. 

 

 

 

풀이법은 아래의 블로그를 참고했다.

https://velog.io/@ju_h2/Python-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-level2-%ED%83%80%EA%B2%9F%EB%84%98%EB%B2%84-BFSDFS

[Python] 프로그래머스 level2 타겟넘버 (BFS/DFS)