BFS/DFS_타겟 넘버_python

문제 설명

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 이하인 자연수입니다.

---

접근방법

문제를 보았을때 왜 BFS인지 DFS인지 감이 잡히질 않았다.

거의 모든 파이썬 풀이 과정을 찾아보면서 BFS DFS 모두 가능하다는 것을 알았지만

DFS로 문제를 풀기로했다.

BFS 코드도 보면 이해가 되긴 하지만

아래 그래프 이미지를 참고하였을때 DFS가 적합하다고 생각했다.

DFS로 루트노드에서 시작하여 리프 노드까지 합을 구하는 과정을 모두 탐색하며 이때 합이 타겟과 같으면 count를 1 증가시키는 방법이다.

프로그래머스 타겟 넘버 (tistory.com)

이번 문제를 풀면서 global 전역변수 사용을 할 수 있는 메서드를 알게되었다. 이걸 몰랐을때는 class로 구성을 해야하나 정말 고민을 많이하였다.

우선, 재귀함수의 base case를 생각하는 건 어렵지 않았다.

주어진 배열의 길이와 인덱스가 같아 질때가 종료하는 조건임과 동시에 타겟과 같은 값을 찾는 조건이 된다.

그 후 재귀함수의 recursive case로 찾고자 하는 합은 value이며, value의 초기값 0으로 함수 실행한다.

첫번째 recursive case인 더하는 함수 호출(완전 탐색)

진행 후, 가장 늦게 호출된 함수자체가 종료조건을 만나며 첫번째 recursive case가 종료되면

두번째 recursive case인 빼는 함수 호출

진행 후, 가장 늦게 호출된 함수자체가 종료조건을 만나며 두번째 recursive case가 종료되고

더한 경우와 뺀 경우 모두 value값과 타겟을 비교하여 count가 증가하며 이를 solution으로 넘겨주면 함수가 종료된다.

count = 0

def dfs(idx, value, numbers, target):
    #전역변수 count 사용 선언
    global count 
    length = len(numbers)
    # 재귀함수 base case
    # 문제가 충분히 작아서 바로 풀수 있는 경우
    # return으로 함수 종료를 해줘야함
    if idx == length:
        if value == target:
            count+= 1
        return 
    
    # 재귀함수 recursive case
    # 재귀적으로 부분 문제를 푸는 경우.
    dfs(idx+1, value + numbers[idx],numbers, target)
    dfs(idx+1, value - numbers[idx],numbers, target)


def solution(numbers, target):
    global count
    dfs(0,0, numbers, target)
    
    return count

---

시간복잡도

주어지는 배열의 갯수가 N일때 N은 2<  N < 20이라고 주어졌다.

자기자신을 총 2번 호출하며 이때 모든 경우의 수를 탐색하기 때문에 O(2^N)이라 할 수 있다.

사실 굉장히 효율이 안좋다고 생각하는데 통과가 주어진 문제를 DFS로 풀었을때 런타임에러가 발생하지 않도록 N값을 낮춘게 아닐까 생각한다.

BFS/DFS 문제의 경우 한눈에 이거다 라고 감이 잡히기엔 많은 시간이 필요할 것 같다.

 

참고 : 프로그래머스 타겟 넘버 (tistory.com)