[프로그래머스] 타겟 넘버 (python) - BFS/DFS

# 문제 

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

 

# 아이디어 

노드 엣지로 구성된 그래프를 그릴 수 있는 상하좌우, map 문제 뿐 아니라 이런 것도 bfs/dfs 문제임을 깨닫게 해준 문제. 이진 트리 형식으로 뻗어나갈 수 있는 문제는 dfs/bfs로 접근할 수 있음을 항상 염두해 두어야겠다. 

이 문제의 접근방식을 손그림으로 표현하면 다음과 같다. 가장 main idea는 +, - 부호에 따른 각 숫자에서 2가지 경우의 수가 생산된다는 것이다. 따라서 numbers의 각 숫자에 따라 2가지 경우로 자손을 뻗을 수 있게되고, 모든 경우의 수를 탐색하는 bfs/dfs 문제가 된다. (여기서 모든 경우의수가 2^n이라는 것을 문제로 추론할 수 있을 것이다. 하지만 numbers의 개수가 20개 이하이므로, 모든 경우를 탐색하는 것도 괜찮은 것 같다. ).

이러한 트리를 너비우선으로 넓게 탐색하면 bfs, 깊게 경우 하나하나 탐색하면 dfs로 해결할 수 있는 것이다. 

 

# Code

우선 BFS로 풀이한 코드는 다음과 같다. 

def solution(numbers, target):
  leaves = [0]          # 모든 계산 결과를 담자      
  count = 0 

  for num in numbers : 
    temp = []
	
    # 자손 노드 
    for leaf in leaves : 
      temp.append(leaf + num)    # 더하는 경우 
      temp.append(leaf - num)    # 빼는 경우 

    leaves = temp 

  # 모든 경우의 수 계산 후 target과 같은지 확인 
  for leaf in leaves : 
    if leaf == target : 
      count += 1

  return count

 

 

다음은 DFS로 풀이한 코드이다. 참고로 DFS는 다음과 같이 작동하는 알고리즘으로, 주로 재귀함수로 구현한다. 코드 내 재귀함수가 무한루프로 돌지 않도록 종료 조건이 있는지 잘 확인하는게 중요하다 ! 

def dfs(numbers, target, idx, values):     # idx : 깊이 / values : 더하고 뺄 특정 leaf 값 
	
    global cnt
    cnt = 0 
	
    # 깊이가 끝까지 닿았으면 
    if idx == len(numbers) & values == target : 
    	cnt += 1
        return 
  
    # 끝까지 탐색했는데 sum이 target과 다르다면 그냥 넘어간다
    elif idx == len(numbers) : 
    	return 
    
    # 재귀함수로 구현 
    dfs(numbers, target, idx+1, values + numbers[idx])   # 새로운 value 값 세팅   
    dfs(numbers, target, idx+1, values - numbers[idx])
 
 def solution(numbers, target) : 
 	
    global cnt
    dfs(numbers, target, 0, 0)
    
    return cnt

위 dfs 코드에 대해 설명을 추가하자면 (사실 내가 잘 이해가 안간다. ㅎㅎ)

• cnt를 global 변수로 지정해줘야한다. solution 함수에서 접근 가능해야하기 때문이다. 
• idx는 DFS의 depth를 나타내는 변수이다. 하지만 이 문제에서 depth는 리스트 원소들의 차례를 의미하므로 리스트의 인덱스로서 작용할 수도 있을 것이다. 따라서 idx 값이 numbers 리스트의 len 값과 같다면 dfs를 중단 해야한다. (재귀함수의 중단조건이 된다)
• DFS 내 values 값을 +, - 로 업데이트 하며 재귀함수가 작용한다. 

 

많이 배웠던 문제인 것 같다 :)