백준 알고리즘 15649 (N과 M(1)) - python

[문제] 백준 알고리즘 15649 (N과 M(1)) - python

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

15649번: N과 M (1)

 

1~N을 이용해서 M개 요소의 조합을 순서대로 만드는 문제. (중복 제거)

DFS(Depth First Search), 백트래킹 구현하는 법을 정확하게 모르는 상태라 한참을 고전했다.

그래서 이번 구현 시에 쓰일 사항들을 간단히 정리해야겠다.

 

1. visited (탐사 했는지 여부)

2. out (탐사 내용)

3. 재귀 함수 시

- 탈출 조건 : Depth가 M일 때

- 탐사를 안했을 경우 진행

- Depth 탐색 전 : 탐사 시작(중복 제거), 탐사 내용 append

- Depth 탐색 후 : 다음 탐사 준비, 탐사 내용 pop

 

개인적으로 어려웠기 때문에 이해한 내용을 코드에 적용하느라 주석 처리가 좀 많다.

 

[Code]

N, M = map(int, input().split())
visited = [False] * N  # 탐사 여부 check
out = []  # 출력 내용

def solve(depth, N, M):
    if depth == M:  # 탈출 조건
        print(' '.join(map(str, out)))  # list를 str으로 합쳐 출력
        return
    for i in range(len(visited)):  # 탐사 check 하면서
        if not visited[i]:  # 탐사 안했다면
            visited[i] = True  # 탐사 시작(중복 제거)
            out.append(i+1)  # 탐사 내용
            solve(depth+1, N, M)  # 깊이 우선 탐색
            visited[i] = False  # 깊이 탐사 완료
            out.pop()  # 탐사 내용 제거

solve(0, N, M)

Python 내부 함수 itertools의 permutations를 이용해서 중복하지 않는 순열을 찾아주는 방법도 있다고 한다.

 

[Code]

from itertools import permutations
N, M = map(int, input().split())
P = permutations(range(1, N+1), M)  # iter(tuple)
for i in P:
    print(' '.join(map(str, i)))  # tuple -> str