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

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

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

 

 

문제 설명

n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

 

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

 

제한사항

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

 

입출력 예

numbers	target	return
[1, 1, 1, 1, 1]	3	5
[4, 1, 2, 1]	4	2

 

 

 

 

Solution

각각의 숫자들을 뺄 때와 더할 때의 모든 경우를 탐색하고 다 더했을 때의 결과가 target과 일치하면 1은 카운트한다.

 

DFS를 사용한 풀이

def solution(numbers, target):
    visited = []
    answer1 = DFS(numbers, target, 0, visited)   # 첫번째 숫자를 더하는 경우
    
    visited = []
    numbers[0] *= -1
    answer2 = DFS(numbers, target, 0, visited)  # 첫번째 숫자를 빼는 경우
    answer = answer1 + answer2
    
    return answer

def DFS(numbers, target, start, visited):
    answer = 0
    visited.append(numbers[start])
    if len(numbers) == start+1: # numbers의 숫자를 다 방문했으면
        # print(visited)
        if sum(visited) == target:  # visited(방문한숫자들)의 합이 target과 맞는지 비교
            return 1    # 맞으면 1 반환(재귀 시 answer에 더해줌)
        else:
            return 0
    else:
        answer += DFS(numbers, target, start+1, visited)  # 다음 노드로 탐색(재귀함수 호출)
        visited.pop()   # 탐색이 끝났으면 마지막으로 방문한 노드 pop
        numbers[start+1] *= -1  # pop한 노드를 빼는 경우도 탐색
        answer += DFS(numbers, target, start+1, visited)
        visited.pop()
        numbers[start+1] *= -1
        return answer

DFS 함수는 탐색할 숫자배열numbers, target, 현재숫자의인덱스start,  방문한숫자visited, case를 인자로 받는다.

 

우선 DFS가 실행되면 현재 숫자를 visited에 추가해준다.

 

현재 숫자를 추가했을 때 다음 숫자의 인덱스(start + 1)가 numbers의 length와 같으면 현재 모든 숫자가 +혹은 -가 붙은 채로 visited에 들어온 것이 된다. 이 때, visited에  들어온 숫자들의 합이 target과 같으면 타겟 넘버를 만들 수 있는 경우의 수를 하나 발견한 것이 된다. (DFS탈출조건)

아직 모든 숫자를 탐색하지 않은 상태라면 다음 숫자에 대해서 DFS 콜백함수를 호출한다.

다음 숫자의 탐색이 끝난 뒤에는 visited에 들어와있던 다음 숫자를 pop 해주고 다음 숫자를 빼는 경우에 대해 다시 DFS 콜백함수를 호출해준다.

 

첫번째 숫자느 일단 넣고 시작하기 때문에 solution 함수에서 첫번째 숫자를 더하는 경우와 빼는 경우에 대해 각각 DFS함수를 수행해주고 두 결과를 더해준다.

 

 

 

BFS를 사용한 풀이

# BFS 풀이
import collections
def solution(numbers, target):
    answer=0
    dq = collections.deque()
    dq.append([numbers[0], 0])
    dq.append([-1*numbers[0], 0])
    
    while dq:
        now, idx = dq.popleft()
        if idx == len(numbers)-1:
            if now == target:
                answer += 1
        else:
            dq.append([now+numbers[idx+1], idx+1])
            dq.append([now-numbers[idx+1], idx+1])
    return answer

재귀함수를 쓰는 DFS보다는 BFS 방식이 더 직관적이고 나은 것 같아서 BFS를 사용한 풀이도 구글링을 통해 참고한 뒤 풀어보았다.

 

numbers의 첫번째 수를 더하는 경우와 빼는 경우를 하나씩 deque에 넣어 주고, 해당하는 인덱스도 묶어서 같이 넣어준다.

그 뒤 popleft를 해가면서 해당 숫자의 다음 인덱스의 숫자를 더해준 것과 빼준 것을 각각 넣어준다.

마지막 인덱스까지 다 더한 수일 때는 target과 일치 여부를 확인해 준 뒤 정답 개수를 카운트한다.