[프로그래머스]타겟넘버-DFS/BFS

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

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

 

DFS 알고리즘 이용

# DFS 알고리즘 이용
def solution(numbers, target):
    cnt = 0
    def dfs(level, sum):
        # 주어진 수를 모두 이용했을때
        if level == len(numbers):
            # 더한 최종 값이 target과 같다면
            if sum == target:
                nonlocal cnt
                cnt += 1
        # 아직 주어진 수를 모두 이용하지 않았을 때
        else:
            # 나머지 경우에 대해 재귀적으로 호출
            dfs(level + 1, sum + numbers[level])
            dfs(level + 1, sum - numbers[level])
    
    dfs(0, 0)
    
    return cnt

 

코드 설명

dfs의 level 과 모두 더한 값은 0으로 초기지정하여 함수를 호출합니다.

1. 만약 주어진 수를 전부 이용했다면 
   1. 더한 최종 값이 target과 일치한다면 1가지의 방법을 찾은 것을 뜻합니다.
2. 아직 주어진 수를 전부 이용하지 않았다면
   1. 더하는 경우를 재귀적으로 호출 (레벨 증가)
   2. 빼는 경우를 재귀적으로 호출 (레벨 증가)
3. 해당 과정을 수행하고나면 몇가지의 방법이 가능한지 구할 수 있습니다.

Point : DFS의 경우 재귀를 통해서 문제를 해결할 수 있다. 해당 문제는 주어진 수를 모두 이용하기만 하면 되는 경우였기에 방문 처리를 따로 해주지는 않았다. 
또한, 덧셈과 뺼셈의 두가지 경우로 재귀를 호출하는 것이 관건이다.

 

BFS 알고리즘 이용

from collections import deque

# BFS 알고리즘 이용
def solution(numbers, target):
    queue = deque()
    cnt = 0
    length = len(numbers)

    def bfs():
        # 덧셈, 뺼셈 2가지의 경우 고려
        queue.append([numbers[0], 0])
        queue.append([-numbers[0], 0])
        
        while queue:
            num, idx = queue.popleft()
            # numbers 배열 끝까지 연산을 수행한 경우
            if idx + 1 == length:
                if num == target:
                    nonlocal cnt
                    cnt += 1
            # 아니라면 연산을 끝까지 수행
            else:
                queue.append([num + numbers[idx+1], idx+1])
                queue.append([num - numbers[idx+1], idx+1])
                
    bfs()

    return cnt

 

코드 설명

초기 큐에 더하는 경우와 빼는 경우 2가지를 추가합니다.

1. 큐가 존재하는 동안 반복합니다.
   1. 만약 주어진 수를 전부 이용한 경우라면
      1. pop 했던 num 과 target이 일치한다면 1가지의 방법을 뜻합니다. (cnt += 1)
   2. 아니라면 큐에 덧셈과 뺄셈에 관한 경우를 큐에 계속 추가하여 줍니다. (주어진 수를 모두 이용하게 하기 위함)

 

Point : BFS의 경우 파이썬의 deque 자료구조를 통해 풀 수 있습니다.

초기 큐에는 DFS와 달리 덧셈과 뺄셈에 대한 2가지의 경우를 append 합니다. 이것을 반복적으로 pop 하면서 문제의 조건과 일치할 때 cnt를 증가시킴으로써 해결할 수 있습니다.