[Baekjoon] 15649번 : N과 M (1) (Python, 백트래킹, dfs)

코드 링크

https://github.com/stellaluminary/Baekjoon

GitHub - stellaluminary/Baekjoon

Contribute to stellaluminary/Baekjoon development by creating an account on GitHub.

github.com

Python

방법 1 - 메모리 30840KB / 시간 240ms / 코드 길이 234B

본 문제는 백트래킹의 기본 예제이다. 백트래킹은 DFS를 통해 가지치기로 살펴볼 수 있는 곳들을 모두 살피는 것이다. 다만 이때 불필요한 곳에서는 탐색을 중지하고 돌아갈 필요가 있다.

DFS는 기본적으로 재귀를 바탕으로 하기때문에 함수 출력 조건을 명시해야하며 특정 조건에 따라 재귀를 시도해야 한다.

본 코드는 이 내용에 모두 부합하도록 구성된 코드로 순열에 대한 출력이 이뤄질 수 있도록 s list에 구성한다.

n, m = list(map(int, input().split()))
s = []

def dfs():
    if len(s) == m:
        print(' '.join(map(str, s)))

    for i in range(1, n+1):
        if i not in s:
            s.append(i)
            dfs()
            s.pop()
dfs()

방법 2 - 메모리 30840KB / 시간 164ms / 코드 길이 357B

def dfs(step):
    if step == m:
        print(' '.join(t))
        return

    for i in range(1, n+1):
        if not visit[i]:
            visit[i] = 1
            t.append(str(i))
            dfs(step+1)
            visit[i] = 0
            t.pop()

import sys
input = sys.stdin.readline
n,m = map(int, input().split())

visit = [0] * (n+1)
t = []
dfs(0)

방법 3 - 메모리 33516KB / 시간 76ms / 코드 길이 155B

itertools.permutations를 통해 바로 순열 조합을 획득할 수 있다.

from itertools import permutations

N, M = map(int, input().split())
li = map(str, range(1, N+1))
print('\n'.join(list(map(' '.join,permutations(li, M)))))