[백준] 1,2,3 더하기(Python) - 백트래킹 & 1차원 dfs 탐색

# 문제 

 

# 입출력 

 

# Idea

이전 문제처럼 1차원 dfs를 이용하는 문제라고 생각했다. 그 이유는 오직 1, 2, 3으로 이루어진 노드의 그래프를 n depth만큼 뻗으면 되는 1차원 dfs로 접근했기 때문이다. 특히, 오직 매번 depth의 노드가 1,2,3으로 이루어지기 때문에 이전 문제와 달리 visited 체크를 하지 않아도 된다고 생각했다. 이러한 아이디어를 그림으로 구체화하면 다음과 같다. 

따라서 만약 위 빨간색 경로의 dfs를 탐색한다면, depth가 깊어질수록 나오는 노드를 점차 cur_sum이라는 변수에 더해서, 만약 cur_sum이 n과 같다면 최종 count를 저장하는 변수에 1을 더하고 재귀함수를 탈출하도록 하면 된다. 그리고 만약 count에 1을 더하고 탈출했다면, 이전 depth의 노드로 거슬러 올라가 다음 depth의 노드로 dfs를 다시 수행하면 된다. 요약하면 다음과 같다. 

• 만약 cur_sum이 n보다 작다면 : dfs 재귀함수를 다음 depth로 계속 수행한다. 
• 만약 cur_sum이 n과 같거나 크다면 : 최종 count 변수에 +1을 하고 dfs 재귀함수를 탈출한다. 그리고 이전 depth의 노드로 돌아가 다시 dfs를 수행한다. 

 

# Code 

위 아이디어를 구현한 코드는 다음과 같다. 위에서 언급한 요약이 if문으로 구현되어 있다. 
특히 마지막 else 문에서 cur_sum에 노드(i)를 더했다가 dfs를 수행하고 다시 빼주는 과정은, 이전 depth의 노드로 돌아가는 과정이라고 생각하면 된다! 

def dfs(cur_sum, n):
  global count 

  # cur_sum이 n과 같으면 count+1 하고 재귀 중단 
  if cur_sum == n : 
    count += 1
    return
  
  # cur_sum이 n보다 크면 바로 재귀 중단 
  elif cur_sum > n :    
    return

  else : 
    for i in range(1, 4):
      cur_sum += i      # 다음 depth의 노드로 뻗는 부분 
      # print('cur_sum : ', cur_sum)
      dfs(cur_sum, n)
      cur_sum -= i      # 이전 depth의 노드로 다시 되돌아가는 역할을 하는 부분
      # print('cur_sum_after : ', cur_sum)

t = int(input())
for _ in range(t):
  n = int(input())    
  count = 0 
  dfs(0, n)
  print(count)

참고로 중간에 cur_sum의 변화 과정을 출력해보면 다음과 같다. (n이 4일 때)