[DFS] 프로그래머스 고득점킷 타켓넘버 - Python 파이썬

 

DFS 깊이 우선 탐색

주어진 numbers를 트리 형식으로 구성하여 탐색해나간다

트리에서 각 stage는 주어진 number의 순서

탐색해 나갈 때, 하나를 끝까지 파고들어서 더한 후에 target과 같은지 확인한다

-> 깊이 우선 탐색을 실시

 

numbers 리스트 아이템을 마이너스로 어떻게?

numbers 리스트의 마이너스들을 저장하기 위한 minus 리스트를 따로 만들어서 관리한다.

기존 numbers에 있는 아이템들은 plus라는 리스트에 복사해 놓은 다음 numbers 리스트 요소들에 -1을 곱해주어서 minus 리스트에 넣어준다.

즉, plus 리스트와 minus 리스트의 인덱스는 서로 같은 numbers의 요소에서 나왔다고 할 수 있다.

 

처음 시작이 Plus가 될수 있고 Minus가 될수 있는데?

처음 더래주는 시작이 Plus가 될 수 있고 minus가 될 수 있기 때문에 각 배열 처음에 0을 넣어주어서 Tree의 root가 0이되어서 아무 상관 없을 수 있도록 해준다.

plus = [0, 1, 1, 1, 1, 1]

minus = [0, -1, -1, -1, -1]

 

재귀하며 Deep 하게 들어가지 않고 return 하는 조건

• 마지막 level 즉 마지막 숫자까지 왔는데, target이 아닌 경우 -> 그냥 Return
• 마지막 Level 즉 마지막 숫자까지 왔는데, target인 경우 -> answer 증가 후 return

def dfs(array, idx, op_sum, target):
    global total_cnt, answer, plus, minus
    
    op_sum += array[idx]
    
    if idx == total_cnt-1: 
        if op_sum == target:
            answer += 1
            return 
        else:
            return 
    else:
        dfs(plus, idx+1, op_sum, target)
        dfs(minus, idx+1, op_sum, target)

def solution(numbers, target):
    global total_cnt, answer, plus, minus
    numbers.insert(0, 0)
    plus = numbers
    minus = [(-i) for i in numbers]
    
    total_cnt = len(plus)
    answer = 0
    
    dfs(plus, 0, 0, target)

    return answer

다른 블로그를 찾아보니 더 간단한 코드도 있어서 공부해보았다

 

굳이 plus minus 분리할 필요 없이 재귀의 과정에서 Number을 더하거나 빼거나 하는 식으로 진행을 하면 된다

 

dfs(idx, sum):
	global answer, numbers, target
    if idx == len(nb):
    	if sum == tg:
        	answer +=1
        return
   	 else :
     	dfs(idx+1, sum+nb[idx]) // sum에 현재 위치의 number을 더하면서 재귀 바로 진행
        dfs(idx+1, sum-nb[idx]) // sum에 현재 위치의 number을 빼면서 재귀 바로 진행
    
    
 def solution(numbers, target):
 	global answer nb, tg
    nb = numbers
    tg = target
    answer = 0
    dfs(0, 0)
    return answer