[백준] 15649번 - N과 M (1) (백트래킹 기초)

참고: https://youtu.be/atTzqxbt4DM

백트래킹

백트래킹?

: 모든 경우의 수를 확인해야 할 때 사용하는 알고리즘

→ for로는 확인이 불가능한 경우 (깊이가 달라질 때)

 

재귀함수 사용

• 재귀함수를 사용하여 1단계를 계속 돌면서
• 2단계에 진입, 2단계를 돌면서 만족하면 return
• 2단계가 모두 끝나면 1단계의 다음 단계 진입
• 계속 재귀적으로 반복하면서 만족하면 return
• 즉, 종료할 return 조건은 항상 코드 상단에 위치할 것

 

백트래킹 시간복잡도

• N^N : 중복이 가능한 경우, N=8까지 가능
• N! : 중복이 불가능한 경우, N=10까지 가능

 

❗백트래킹 Tip

• 백트래킹 문제는 N이 작음 (N이 보통 10 언저리)
• 재귀함수 사용할 때, 종료 시점 잊지 않기!

 

백준 15649번

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

N, M = map(int, input().split())
result = []
chk = [False] * (N+1)

def recur(num):
  if num == M:
    print(' '.join(map(str, result)))
    return
  for i in range(1, N+1):
    if chk[i] == False:
      chk[i] = True
      result.append(i)
      recur(num+1)
      chk[i] = False
      result.pop()

recur(0)

 

1) 아이디어

• 1부터 N중에 하나를 선택한 뒤,
• 다음 1부터 N까지 선택할 때 이미 선택한 값이 아닌 경우 선택 (재방문여부)
• M개를 선택할 경우 출력

2) 시간복잡도

• N! >> 최대 8까지 이므로 가능 (중복없이)

3) 자료구조

• 방문 여부 확인 : bool[]
• 선택한 값 입력: int[]

 

노션(Notion) 정리

: https://fast-receipt-fe1.notion.site/4956757cb8c344ebaab580ee880ab7f6

백트래킹

 

화이팅 💪