백준 알고리즘 15650 [파이썬]

 

문제

문제풀이

import sys
read = sys.stdin.readline
N, M = map(int, read().split())
lst = [i for i in range(1, N+1)]
check_list = [False]*N

arr = []
def dfs(cnt):
  if cnt == M:
    print(*arr)
    return
  
  for i in range(N):
    if check_list[i]:
      continue
    check_list[i] = True
    arr.append(lst[i])
    dfs(cnt+1)
    arr.pop()
    

    for j in range(i+1, N):
      check_list[j] = False

dfs(0)

 

  if cnt == M:
    print(*arr)
    return

M이 수열의 길이 이기 때문에 arr리스트의 길이를 cnt가 나타내고 cnt ==  M일 때 arr을 print합니다. 리스트 형식으로 print를 하면 안되기 때문에 arr앞에 *을 붙이면 리스트 형식으로 print되지 않고 숫자들만 나열되어서 나옵니다. 

 

  for i in range(N):
    if check_list[i]:
      continue
    check_list[i] = True
    arr.append(lst[i])
    dfs(cnt+1)
    arr.pop()
    
    for j in range(i+1, N):
      check_list[j] = False

check_list[i]가 True로 되어있으면 lst[i]를 더이상 arr에 넣을 수 없다. False이면 True로 바꾸고 lst[i]를 arr에 append한다. 그다음 dfs(cnt+1) 재귀함수를 사용해서 M 길이만큼의 순열을 arr안에다가 만든다. 만들고 print를 하면 arr.pop()을 해서 뒤에 숫자를 빼고 또 다른 숫자를 넣어서 새로운 순열값을 만든다.

 

그 밑에 for loop은 숫자를 다시 사용해야되기 때문에 True로 바뀌어 있었던 것들은 다시 False로 바꿔줍니다. 하지만 순열이 오름차순이기 때문에 사용이끝난 lst[i] 숫자는 더이상 사용하면 안되기 때문에 check_list[i+1]부터 False로 바꿔줍니다.