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

15649번: N과 M (1)

 

 

코드

n, m = map(int,input().split())
s = []
visit = [False] * (n+1)
def dfs():
	if len(s) == m:
		print(*s)
		return
	
	for i in range(1,n+1):
		if visit[i] == False:
			visit[i] = True
			s.append(i)
			dfs()
			s.pop()
			visit[i] = False
		
dfs()

 

설명

백트래킹 문제는 처음 풀어봐서 다른 사람들의 풀이를 참고했다.

DFS와의 차이점은 DFS는 전부 검색하지만, 백트래킹은 방법이 아니면 중간에 나온다.

visit를 통해 이미 방문했는지 체크를 해줬고, s의 길이가 m과 같아질 때까지 s에 숫자를 넣어줬다. s를 출력해준 후에는 s.pop()을 통해 리스트에서 빼주고 visit를 다시 false로 바꿔준다.