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

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

15649번: N과 M (1)

import sys
read = sys.stdin.readline

def dfs():
  if len(s) == m:
    print(' '.join(map(str,s)))
    return
  for i in range(1, n+1):
    if visited[i]:
      continue
    visited[i] = True
    s.append(i)
    dfs()
    s.pop()
    visited[i] = False

n, m = map(int, read().split())
s = []
visited = [False] * (n+1)
dfs()

백트래킹을 이용하는 문제다. 

다중 for문으로 해결하기엔 수가 커지면 복잡해지기 때문에 백트래킹을 사용해야 한다.

 

visited 배열을 이용해 n까지의 수 중 사용한 수를 체크 한다. 

사용하지 않은 수면 배열 s에 넣어 s의 길이와 m과 같을 때 출력한다.

 

아직 혼자 힘으로 해결하지 못해 구글링의 힘을 빌린다....😂

 

참고 url: https://velog.io/@yusuk6185/%EB%B0%B1%EC%A4%80-15649-N%EA%B3%BC-M-1-%ED%8C%8C%EC%9D%B4%EC%8D%AC-with-%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9

[백준 15649] N과 M (1) - 파이썬 with 백트래킹