[프로그래머스] 코딩테스트 연습깊이/너비 우선 탐색(DFS/BFS)타겟 넘버

문제

문제 설명

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 함수를 작성해주세요.

 

입력 & 출력

입출력 예

numberstargetreturn

[1, 1, 1, 1, 1]	3	5
[4, 1, 2, 1]	4	2

 

풀이 과정

문제에 대놓고 재귀로 풀라고 나와있는데 DFS가 아닌 이중 for문으로 해결하는 방식으로 생각해서 모든 배열에 1을 넣어둔 상태에서 -1을 차례대로 넣고 zip()을 이용해서 두 배열에서 숫자를 뽑아서 해결하는 방식으로 풀이를 하다가 재귀 방식으로 선회하였다.

 

1. 재귀를 이용한 풀이를 하는 것이 포인트인 문제 일단 재귀문 안에서 공유되어야 하는 answer 변수는 global로 선언하여서 어떤 함수에서 실행되고 증가되어도 공유가 될 수 있게 해 두었다. 해당 내용은 함수의 파라미터로써 넣어서 사용하려고 했는데 문제에서 제시한 파라미터의 숫자와 맞지 않는다고 하여서 이렇게 구성하게 되었다.

2. 함수가 돌고 다시 자기자신을 호출할 수 있는 구조로 되어서 모든 경우를 다 탐색하여야 한다. 이때 경우의 수는 모든 탐색이 끝나서 idx의 갚고 numbers 배열의 길이가 같아져서 재귀 문을 탈출하는 경우와 모두 탐색을 못해서 재귀 함수가 돌아가야 하는 경우로 나눠져야 된다고 생각했다.

3. 이렇게 구성되었을때 숫자를 더할 때와 뺄 때의 두 가지 경우가 생기게 되므로 idx를 다 돌지 않았을 때는 이 두 가지 경우를 재귀 문으로 호출해주고 각 result에서 해당 경우를 표현해서 넣어주게 되면 모든 경우에 대한 탐색이 되게 된다.

 

코드

answer = 0


def dfs(idx, result, numbers, target):
    global answer
    if idx == len(numbers):  # numbers 원소를 모두 계산했을 경우
        if result == target:
            answer += 1
        return answer
    else:
        dfs(idx + 1, result + numbers[idx], numbers, target)  # 재귀구조
        dfs(idx + 1, result - numbers[idx], numbers, target)


def solution(numbers, target):
    global answer
    dfs(0, 0, numbers, target)  # result = 0으로 초기화

    return answer