[알고리즘] 타겟넘버 (DFS, BFS)

타겟넘버

(문제)

DFS 깊이우선탐색으로 주로 이동과정의 계산을 할때 사용 (Stack)
BFS 너비우선탐색으로 주로 최단거리를 계산할때 사용 (queue)사용
BFS 사용시 from collections import deque 추가

우선 항목이 BFS/DFS의 탐색이여서 해당 탐색을 이용해서 문제를 풀어보자

DFS 구현.

def solution(numbers, target):
   
   # DFS
   # 최상단 Node 선언
   visited = [0]
   
   for number in numbers:
       temp =[]
       for i in visited:
           # +1 과 -1 뿐
           temp.append(i+number)
           temp.append(i-number)
           visited = temp
       print(visited)
   return visited.count(target)

             0
        +1     -1
     +1-1     +1 -1
  +1-1 +1-1 +1-1 +1-1
       numbers 만큼

visited 값 :
[5, 3, 3, 1, 3, 1, 1, -1, 3, 1, 1, -1, 1, -1, -1, -3, 3, 1, 1, -1, 1, -1, -1, -3, 1, -1, -1, -3, -1, -3,-3, -5]

visited 값 중에 Count를 이용하여 target 값 구하기

BFS 구현

BFS구현에 대한 이해도가 부족해서 해당분의 출처를 이용하였다.
출처 : https://jainn.tistory.com/139?category=913177

from collections import deque

def solution(numbers, target):
    answer = 0
    queue = deque()
    #최상단노드
    queue.append(0)
    
    for number in numbers:
        for _ in range(len(queue)):
            n = queue.popleft()
            queue.append(n+number)
            queue.append(n-number)
    
    return queue.count(target)

deque 는
[0][1 -1][-1 2 0][2 0 0 -2][0 0 -2 3 1]
순으로 들어옴.

BFS경우는 큐를 사용하기때문에 제일앞에있는 값을 뺀후, 인접한 값들을 추가해주는 방식