[백준] 15649번: N과 M(1) - Python

링크: https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

아이디어

• 백트래킹사용
• for문을 돌며 숫자를 선택
• 방문여부를 확인하며 돌고 다시 이전 깊이로 돌아갈 때 방문여부를 되돌려줘야함
• M개의 숫자를 고른 경우의 경로는 print해준다.

시간복잡조

• 중복을 허용하지 않은 경우니 N!이다 -> 가능!

구현

import sys

# 백트래킹 구현
def back():
    # 경로를 찾았을 때 출력
    if len(check) == m:
        for i in check:
            print(i, end=" ")
        print()
    for i in range(1, n+1):
        if i not in check:
            check.append(i)
            back()
            check.pop()

input = sys.stdin.readline

n, m = list(map(int, input().split()))

check=[]

back()

마무리

• 백트래킹의 개념을 찾아보고 문제를 푸니 dfs와의 혼란은 어느정도 해결이 된 듯 하다.
• 이제는 문제를 많이 풀어 양으로 익숙해지는 일만 남았다..