https://www.acmicpc.net/problem/15649
15649번: N과 M (1)
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해
www.acmicpc.net
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과 같을 때 출력한다.
아직 혼자 힘으로 해결하지 못해 구글링의 힘을 빌린다....😂
[백준 15649] N과 M (1) - 파이썬 with 백트래킹
https://www.acmicpc.net/problem/15649백트래킹 알고리즘의 기본 예제이다. 백트래킹은 DFS를 사용하여 풀 수 있는데, 일반적인 DFS와의 차이점은 가지치기를 한다는 점이다. 모든 경우의 수를 탐색하는 대
velog.io
'Algorithm > Problems' 카테고리의 다른 글
| [백준/파이썬] 15651번 N과 M(3) (0) | 2023.02.01 |
|---|---|
| [백준/파이썬] 15650번 N과 M (2) (0) | 2023.02.01 |
| [백준/파이썬] 1012번 유기농 배추 (0) | 2022.12.06 |
| [백준/파이썬] 11478번 서로 다른 부분 문자열의 개수 (0) | 2022.12.06 |
| [백준/파이썬] 10816번 숫자 카드2 (0) | 2022.11.18 |