[프로그래머스] 타겟 넘버 [Level 2] (python 파이썬) (DFS,BFS)

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

프로그래머스

 

 

#DFS로 푸는 경우



def solution(numbers, target):
  
    ans = 0
    def dfs(num, index):
        nonlocal ans   
        if index == len(numbers):
            if num == target:
                ans = ans +1
            return 0
        else:
            dfs(num+numbers[index], index+1)
            dfs(num-numbers[index], index+1)

    dfs(0,0)
    return ans

 

 

 

 

 

 

# BFS로 푸는 경우



def solution(numbers, target):
    stack = [[numbers[0],0], [-numbers[0],0]]
    ans = 0

    while stack:
        i = stack.pop()
        num, index = i[0], i[1]
        if index == len(numbers) -1:
            if num == target:
                ans+=1
        else:
            stack.append([num+ numbers[index+1], index+1])
            stack.append([num- numbers[index+1], index+1])

        
    return ans

 

 

 

 

이 문제는 전형적인 DFS, BFS 문제이다. 

 

이러한 그래프 탐색 알고리즘의 대표적인 유형으로는 

1. 경로탐색 유형 (최단거리, 시간)

2. 네트워크 유형 (연결)

3. 조합 유형 (모든 조합 만들기)

 

위와 같은 유형 중 이 문제는 3번인 조합 유형에 해당한다. 

 

각각의 수는 모두 양수와 음수의 경우를 가질 수 있으므로, N개의 수일 경우 N**2의 경우의 수가 가능할 것이다.

 

 

[1,1,1] 을 예시로 둬보자.

 

 

위의 경우 각각의 1은 모두 음수와 양수의 경우의 수를 가진다. 

 

즉

 

           3   

     2     

           1   

1

           1

     0

          -1

 

과

 

          1 

     0     

          -1   

-1

          -1

     -2

          -3

 

 

 

총  8 가지의 경우가 나올 수 있다. (2**3)

 

 

 

이런 식으로 numbers를 돌면서 첫번째 부터 마지막 수까지 더한값과 뺀값을 넣은 후 마지막 연산의 결과와 target값을 비교하면 된다.

 

 

 

위의 경우를 보면 그래프의 모양과 흡사하다.

 

 

이 경우 그래프 탐색 알고리즘인 DFS 와 BFS를 사용하면 효과적으로 문제를 해결할 수 있다.

 

 

DFS, BFS의 흐름

 

 

 

 

 

 

 

 

BFS 로 푸는 경우

 

1. 스택에 [첫번째수, 0(첫번째 인덱스)] 를 넣고 시작한다.

2. while 문 동안 스택에서 한 가지 경우를 빼고, 그 인덱스가 마지막 연산의 결과이면 target과 비교해서 ans를 갱신한다.

3. 만약 그 인덱스가 마지막 연산이 아닌, 연산 도중의 경우인 경우, 스택에 다음 연산 값을 집어 넣는다. + (인덱스 +=1)

(다음 연산값 = 스택의 [현재값, 현재 인덱스] 중 현재값에 다음 값을 더한값)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

DFS로 푸는 경우

 

#재귀함수를 사용하여 마지막 경우에 다다를때까지 함수를 타고 들어간다.

 

재귀함수: (총합, 현재 인덱스)

1. 만약 현재 인덱스가 마지막 인덱스이면, 총합과 target 값을 비교하여 ans를 갱신한다.

2. 만약 현재 인덱스가 마지막 인덱스가 아니라면 (중간 연산), 지금까지의 총합에 현재 인덱스번째 수를 더해(또는 빼서) 총합을 갱신하고, 다음 인덱스와 함깨 다음 함수를 호출한다.

2-1 다음 값을 더하는 경우와 빼는 경우를 모두 구하기 위해 첫줄에는 더하는 경우, 두 번째는 빼는 경우를 고려한다.