프로그래머스_python lv2. 타겟 넘버(깊이/너비 우선 탐색(DFS/BFS))

<문제 링크>

https://school.programmers.co.kr/learn/courses/30/lessons/43165?language=python3

프로그래머스

 

<정답 코드>

sol 1) BFS(너비 우선 탐색)

from collections import deque
 
def solution(numbers, target):
    answer = 0
    q = deque()
    n = len(numbers)
    
    q.append([numbers[0], 0])
    q.append([-1 * numbers[0], 0])
 
    while q:
        tmp, idx = q.popleft()  # q의 원소들 뽑아서 확인
        idx += 1
        
        if idx < n:             # 아직 모든 원소 사용 x
            q.append([tmp + numbers[idx], idx])
            q.append([tmp - numbers[idx], idx])
        else:                   # 모든 원소 사용 완료  
            if tmp == target:   # 조합으로 target값 만들어졌는지 확인
                answer += 1
    return answer

BFS로 풀이한 경우

if)

deque q에서 맨 앞의 원소를 뽑아

다음 원소와의 연산 결과가 +일때와 -일때를 계산하고 q에 추가하는 방법으로 최종 연산 결과 가능한 모든 수를 구함

 

else)

모든 연산이 끝나면 맨 앞부터 원소를 뽑아 target과 일치하는지 확인 후, 일치하면 answer 값 +1

 

 

 

 

sol 2) DFS(깊이 우선 탐색)

answer = 0
 
def DFS(idx, numbers, target, value):
# idx : 현재 숫자의 index, value : 현재까지 계산된 숫자의 합
    global answer       # global 변수로 선언해 재귀 호출 간 값 유지/업데이트
    n = len(numbers)
    if idx == n and target == value:    # 모든 숫자 처리(idx == n) + 현재 값이 타겟과 일치(target == value)
        answer += 1
        return
    if idx == n:                        # 모든 숫자 처리 후 타겟과 불일치하면 재귀호출 종료
        return
    
    # 현재 idx 숫자를 value에 더하고/빼고 다음 숫자로 넘어감
    DFS(idx+1, numbers, target, value+numbers[idx])
    DFS(idx+1, numbers, target, value-numbers[idx])
 
def solution(numbers, target):
    global answer
    DFS(0, numbers, target, 0)
    
    return answer

 

재귀적 함수 호출을 사용해 DFS 방식으로 탐색하는 코드