[코딩테스트] 깊이/너비 우선 탐색(DFS/BFS) - 타겟 넘버

---

문제

 

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

프로그래머스

 

문제 예시

주어진 numbers를 차례로 더하거나 빼서 target이 되는 방법의 수를 구하는 문제

 

제한사항이 타이트하지 않아서 다양한 풀이가 가능하다.

 

---

전략

 

01. BFS

 가장 처음 생각난 건 BFS다. queue에 (값, 순서)를 넣고 차례차례 꺼내서 더하고 빼준 뒤 다시 queue에 넣어준다. 마지막 순서까지 끝났다면 target값과 같은지 체크하는 방법이다.  

 

 

---

풀이

 

from collections import deque

def solution(numbers, target):
    limit = len(numbers)
    
    queue = deque([(0, 0)])
    
    count = 0
    
    while queue:
        value, depth = queue.popleft()
        
        if depth == limit:
            if value == target:
                count += 1
            continue
        
        queue.append((value + numbers[depth], depth + 1))
        queue.append((value - numbers[depth], depth + 1))
    
    return count

 

 정석적인 BFS풀이다.

---

다른 사람의 풀이

 

01. DFS

 

def solution(numbers, target):
    if not numbers and target == 0 :
        return 1
    elif not numbers:
        return 0
    else:
        return solution(numbers[1:], target-numbers[0]) + solution(numbers[1:], target+numbers[0])

 

 solution함수 자체를 재귀적으로 호출하면서 numbers의 범위를 앞에서 하나씩 줄여나가고, 값 자체는 target에서 빼줘서 마지막에 target이 0이 됐다면 1을 리턴, 아니면 0을 리턴하고 그 값들을 더해서 풀었다. 재귀를 이용한 깔끔한 풀이다.

 

 

02. 완전탐색

 

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)

 

 itertools 라이브러리의 중복순열 함수인 product를 이용해 +x, -x의 모든 경우의 수를 조합해 map함수를 이용해 각각을 더해주고 target이 되는 경우의 수를 count해주었다.