프로그래머스 DFS (타겟 넘버) - Python

문제 

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

프로그래머스

 

 

 

• 소스코드 DFS

answer = 0
def dfs(idx,sum,numbers,targer):
    global answer
    if idx == len(numbers) and targer == sum:
        answer +=1
        return
    if idx == len(numbers):
        return

    dfs(idx+1,sum+numbers[idx],numbers,targer)
    dfs(idx+1,sum-numbers[idx],numbers,targer)

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


print(solution([1, 1, 1, 1, 1],3))

 

 

 

• 소스코드 스택

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

    count = 0

    while stack:
        idx, current_sum = stack.pop()
        if idx == len(numbers):
            if current_sum == target:
                count += 1
        else:
            stack.append((idx + 1, current_sum + numbers[idx]))
            stack.append((idx + 1, current_sum - numbers[idx]))

    return count

print(solution([1, 1, 1, 1, 1], 3))

 

 

 

• 해설

이 문제는 프로그래머스 2레벨 의 문제이다. 처음 이문제를 보았을 때, 

접근 해야할 방식이 많아 보였다.(스택,슬라이딩 윈도우,DFS,BFS) 

 

필자는 먼저 스택으로 풀어 보았을때 풀면서 DFS랑 다를게 없어 보였다. 스택 보다는 지금 DFS를 공부를 하는 중이여서 설명은 DFS를 위주로 설명을 하려고 한다.

 

 

 

 

 

 

 

 

일단 DFS 코드의 실행 순서를 끄적여 보았을 때,

나만 알아볼 거 같다....

간단하게 3개의 numbers에 target이 1 이라고 했을때 코드의 DFS 시작은 0,0 으로 시작 한다 DFS(index,sum,생략,생략)

 첫 DFS 들어왔을 때 조건은 일치하지 않으므로 

dfs(idx+1 , sum + numbers[idx], ,) 으로 들어와 아래 있는 dfs(idx+1 , sum - numbers[idx], ,) 이 구문은 대기한다.

이 때 재귀함수이므로 재귀함수는 dfs(1,1)은 sleep상태로 들어가 대기한다. 다음으로 dfs(1,1) 의 조건이 일치 하지않아 dfs(2,2) 로 들어 간다 -> 조건이 일치 할때 까지 탐색을 하는데 dfs(3,3) 이때 인덱스가 numbers 배열의 끝까지 도착 했으므로 return 을 하고 그 이전 sleep 상태인 

dfs(3,3) 함수의 다음줄 인 dfs(2+1, 2 - numbers[2]) 가 실행 된다

 

쭉 이런식으로 진행 하였을 때 DFS 는 idx 가 len(numbers) 와 같고 target 이 누적합이랑 같을 경우 global 변수의 answer를 증가시켜 답을 구해 간다.

 

 

 

 

 

 

 

DFS 는 손으로 직접 작성해가면서 실행과정을 알가는 것이 공부할 때 이해가 가기 쉽다. 

DFS 함수의 실행과정이 스택프레임을 이해하면서 공부하는 중이다..!

 

 

 

• 참고 블로그

https://velog.io/@jhjcoding/1.-%EC%9E%AC%EA%B7%80%ED%95%A8%EC%88%98%EC%8A%A4%ED%83%9D%ED%94%84%EB%A0%88%EC%9E%84

[DFS] 1. 재귀함수(스택프레임) ★