백준 15649번(N과M(1)) 파이썬

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

15649번: N과 M (1)

이 문제는 백트래킹 문제이다. 백트래킹은 dfs에서 주로 응용되는 알고리즘이다.

방문 후에 다시 미방문 처리를 해주는 알고리즘 이다.

난이도 꽤 있는 알고리즘이라고 말 할 수 있다. 코딩테스트에도 자주 나오는 유형이니 꼭 짚고 넘어가야한다.

아래 코드에 주석을 달아 설명해 놓았다.

import sys
input = sys.stdin.readline

n,m = map(int,input().split())
ans = []
visited = [False]*(n+1)

def dfs():
    if len(ans) == m: # 조건처럼 리스트의 길이가 m이 되면 출력해준다
        print(' '.join(map(str,ans)))
        return
    for i in range(1,n+1):
        if visited[i]: # 방문했을경우 continue 해준다
            continue
        visited[i] = True # 미방문일경우 방문처리를 해준다
        ans.append(i) # 그리고 리스트에 추가해준다
        dfs() # 이어서 dfs문을 재귀함수로 실행한다
        ans.pop() # 마지막에 추가됐던 수를 빼준다.
        visited[i] = False # 여기가 중요!!!! 방문했던곳을 다시 미방문 처리 해준다
        
        
dfs()