[프로그래머스/Python] 타겟 넘버 - Level2

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

코딩테스트 연습 - 타겟 넘버

이 문제는 깊이 우선 탐색(DFS) 를 사용하면 되는 문제였다. 왜 DFS를 사용하면 되는지에 대한 설명은 다음과 같다.

 

출처 - 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

 

처음에는 dfs 메서드를 solution 밖으로 뺐었는데 뭔가 자꾸 에러가 나서 그냥 바꿨다... 

def solution(numbers, target):
    answer = 0
    n = len(numbers)
    
    # 깊이 우선 탐색 실행 메서드
    def dfs(idx, result):
        if idx == n: # 더 이상 탐색할 값이 없을 때
            if result == target: # target 값과 같다면 answer에 +1 
                nonlocal answer
                answer += 1
            return
        else: # 탐색할 값이 남았을 때 계속 dfs 호출
            dfs(idx + 1, result + numbers[idx])
            dfs(idx + 1, result - numbers[idx])
            
    dfs(0,0) # 깊이 우선 탐색 시작
    
    return answer

dfs() 는 깊이 우선 탐색을 실행하는 메서드이다. 더 이상 탐색할 값이 없고, 탐색이 끝난 결과 값인 result 가 target 값과 같다면 answer에 +1을 한다. 탐색할 값이 남았다면 계속 dfs() 메서드를 호출하여 깊이 우선 탐색한다. dfs(0,0) 을 호출하여 깊이 우선 탐색을 시작하면 된다. 

 

이 문제는 처음 봤을 때 굳이 DFS로 풀지 않아도 될 것 같다고 생각했어서 다른 사람들의 풀이를 찾아보니 풀이 방법이 다양했다.

 

1. 완전 탐색 

from itertools import product
def solution(numbers, target):
    l = [(x, -x) for x in numbers]
    s = list(map(sum, product(*l)))
    return s.count(target)

 

2. 너비 우선 탐색 (BFS)

from collections import deque
def solution(numbers, target):
    answer = 0
    queue = deque()
    n = len(numbers)
    queue.append([numbers[0],0])
    queue.append([-1*numbers[0],0])
    while queue:
        temp, idx = queue.popleft()
        idx += 1
        if idx < n:
            queue.append([temp+numbers[idx], idx])
            queue.append([temp-numbers[idx], idx])
        else:
            if temp == target:
                answer += 1
    return answer