프로그래머스 - 타겟 넘버 (BFS, DFS 고득점 키트)

BFS를 생각하면 흔히 격자에서 상하좌우를 탐색하는 알고리즘을 떠올리게 된다.

하지만 이는 2차원 격자 문제에서의 BFS응용일 뿐이다.

 

본질은 BFS란 가장 가까운 상태부터 탐색해 나가는 알고리즘이란 것이다.

 

트리, 그래프, 문자열, 배열, 상태공간 등 모든 탐색가능한 구조에서 사용 가능하다.

 

---

 

이 문제는 덧셈, 뺄셈 두가지가 가능하다는 점에서 트리구조의 BFS활용을 사용할 수 있다.

 

2차원 배열의 BFS에서는 상태표현을 x, y 좌표와 상하좌우 4방향으로 한다고 하면,

이 문제에서는 현재 인덱스와 누적된 합계를 인잘 넣어주고, 방향은 + - 두가지인 셈이다.

 

다만 차이점이라면 2차원 배열에서의 움직임은 방문처리를 통해 이미 갔던곳은 못가게해야하지만, 지금 문제같은 경우는

같은 수가 나오더라도 +와 -의 조합이 달라지면 다른케이스로 치기 떄문에(최단경로를 구하는것이 아니기 때문) visited가 필요없다.

 

또한 시간복잡도도 N*M과는 다르게 2**n이 필요하다.

 

from collections import deque

def solution(numbers, target):
    queue = deque()
    queue.append((0, 0))
    count = 0
    
    while queue:
        index, curr_sum = queue.popleft()
        if index == len(numbers):
            if curr_sum == target:
                count += 1
        else:
            queue.append((index + 1, curr_sum + numbers[index]))
            queue.append((index + 1, curr_sum - numbers[index]))
            
    return count

 

큐를 만들어주고, 0, 0을 넣어준다.

인덱스가 0일떄 현재의값도 0이다.

 

예시가 [1,1,1,1,1]이라면 else구문의 append두번으로 인덱스1 즉 첫번쨰 원소인 1을 0에서 더하거내 빼준다.

그럼 첫번째 while문에서 첫번째 원소 1을 더하고 뺀 +1, -1이 1인덱스에 큐로 들어가게 된다.

 

- 첫번째 while문을 돌고 난 뒤의 큐상태

(1,1) (1,-1)

 

그럼 두번쨰 while문에서 index는 2가되고, 두번쨰 원소인 1을 각 큐 원소에 더하고 뺀 2, 0, -2가 추가로 들어가게 된다.

(2,2) (2,0) (2,-2)

 

이런식으로 numbers의 인덱스 끝까지 가게되면 if문의 index == len(numbers)에 걸리게 되고, 그때 값이 target인

여러 가지들이 모두 걸려 count에 반영되게 된다.