백준 10974번 모든 순열(Python3)
def dfs(cnt):
if cnt == n:
print(*lists)
return
for i in range(n):
if check[i]:
continue
lists.append(num_lists[i])
check[i] = True
dfs(cnt + 1)
lists.pop()
check[i] = False
n = int(input())
lists = []
num_lists = [i + 1 for i in range(n)]
check = [False] * n
dfs(0)
문제 :
해결 방법 : 백트래킹을 통해 모든 경우의 수를 탐색하여 순열을 구해주었다!
-
[] 빈 리스트에서 시작.
-
[1, ] 처음엔 check리스트가 모두 false이므로 1이 들어감.
check = [true, flase] -
재귀함수를 만나 cnt = 1이 되어 재귀
-
lists = [1, 2]
check = [true, true, false] -
또 재귀. cnt = 2
-
lists = [1, 2, 3]
check = [true, true, false] -
재귀. cnt = 3
if cnt == n에서 걸리므로
print를 하고 return -
return 하여 재귀함수 밑의 코드 진행.
lists = [1, 2]
check = [true, true, false] -
이런 방식으로 쭉 반복하며 if문에 걸릴때마다 순열을 출력한다.
Author And Source
이 문제에 관하여(백준 10974번 모든 순열(Python3)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@tjdwns5063/백준-10974번-모든-순열Python3저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)