본문 바로가기
백준 알고리즘(BOJ)

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

by Think_why 2019. 10. 15.

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

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

 

15649번: N과 M (1)

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다.

www.acmicpc.net

 

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
728x90

댓글