[프로그래머스 43165 파이썬] 타겟 넘버 (level 2, DFS/BFS)

알고리즘 유형 : DFS/BFS
풀이 참고 없이 스스로 풀었나요? : O

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

SOLVE 1

DFS 풀이

def DFS(n, order, numbers, target):
    if order == len(numbers)-1:
        if n == target:
            return 1
        
        return 0
    
    case1 = DFS(n+numbers[order+1], order+1, numbers, target)
    case2 = DFS(n-numbers[order+1], order+1, numbers, target)
    
    return case1 + case2

def solution(numbers, target):
    return DFS(numbers[0], 0, numbers, target) + DFS(-numbers[0], 0, numbers, target)

SOLVE 2

BFS 풀이

from collections import deque

def solution(numbers, target):
    answer = 0
    
    q = deque()
    q.append((numbers[0], 0))
    q.append((-numbers[0], 0))
    
    while q:
        n, order = q.popleft()
        
        if order == len(numbers)-1:
            if n == target:
                answer += 1
            continue
        
        q.append((n+numbers[order+1], order+1))
        q.append((n-numbers[order+1], order+1))
    
    return answer

풀이 요약

1. 전형적인 BFS or DFS 문제이다.

   다만 numbers의 첫 번째 숫자, 두 번째 숫자, 등등으로 한 칸씩 나아가는 단방향 그래프의 탐색이므로, 이미 방문한 노드가 도착 노드인 경우를 거르기 위해 visited 배열을 사용할 필요가 없다.

2. 탐색은 두 갈래로 나아간다. 현재 수에 다음 수를 더하거나 빼거나.

   이 때 numbers의 몇 번째 수를 탐색중인지를 나타내는 order도 고려해서 매개변수로 넣어주자.

   그렇게 탐색하다가 어떤 노드의 order가 numbers에서의 마지막 순서일 때 그 값이 target과 같다면 카운팅을 해준다.

배운 점, 어려웠던 점

• 기본적인 BFS, DFS 문제라 쉬웠다. 빠른 구현을 연습하는 데 도움이 됐다.