15650번: N과 M (2)
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해
www.acmicpc.net
<내 코드>
N, M = map(int, input().split())
visited = [0 for _ in range(N)]
arr = []
def dfs(cnt):
if cnt == M:
print(*arr)
return
for i in range(N):
if visited[i] == 0:
visited[i] = 1 # 중복 제거
arr.append(i+1)
dfs(cnt+1) # 다음 깊이 탐색
arr.pop() # 탐사한 내용 제거
# 순열 부분과의 차이점
for j in range(i+1, N):
visited[j] = 0
dfs(0)
처음 i의 DFS 탐색에 사용 된 i값을 제외시키는 것이 순열과 다른 조합의 차이다.
파이썬 itertools 모듈의 combinations를 사용한 방법
from itertools import combinations
N, M = map(int, input().split())
p = combinations(range(1, N+1), M)
for i in p:
print(*i)반응형
'알고리즘 문제풀기 > 백준 - Python' 카테고리의 다른 글
| [백준 15652] N과 M (4) - Python (백트래킹, DFS) (0) | 2020.10.27 |
|---|---|
| [백준 15651] N과 M (3) - Python (백트래킹, DFS) (0) | 2020.10.26 |
| [백준 15649] N과 M(1) - Python (백트래킹, DFS, 순열) (0) | 2020.10.26 |
| [백준 14226] 이모티콘 - Python (BFS, DP) (0) | 2020.10.25 |
| [백준 1261] 알고스팟 - Python (우선순위 큐, BFS) (0) | 2020.10.24 |