문제 요약
자연수 1..N에서 길이가 M인 수열을 모두 출력한다.
- 중복 선택 가능 (같은 수 여러 번 가능)
- 출력은 사전 순(lexicographic) 증가
내가 느낀 점
이전의 [BOJ 15650] N과 M (2) 를 다시 공부하고 나서 풀어보니, 전체 구조가 거의 똑같아서 훨씬 쉬웠다.
다만 아직 “백트래킹 감”이 완전히 몸에 붙은 건 아니라서, 이번 문제 코드를 한 줄씩 뜯어보면서 개념을 정리해보려 한다.
내 코드
n, m = map(int, input().split())
path = []
out = []
def dfs(start):
if len(path) == m:
out.append(' '.join(map(str, path)))
return
for x in range(start, n + 1):
path.append(x)
dfs(start)
path.pop()
dfs(1)
print('\n'.join(out))
코드 뜯어보기: 백트래킹이 뭔지 “구조”로 이해하기
1) path는 “현재까지 만든 수열”
path = []
- 재귀가 내려갈수록(
dfs가 더 깊어질수록)path길이가 늘어난다. path는 항상 “지금까지 선택한 숫자들의 리스트”다.
예를 들어 n=3, m=2일 때,
- 첫 단계에서
path = [1]을 선택하고 - 다음 단계에서
path = [1, 1],path = [1, 2],path = [1, 3]… 이런 식으로 확장된다.
2) 종료 조건: 길이가 M이면 출력 후보 완성
if len(path) == m:
out.append(' '.join(map(str, path)))
return
- 백트래킹은 “완성 조건”이 가장 중요하다.
- 여기서는 길이가
m이 되는 순간이 “완성”이다. - 완성되면 문자열로 만들어
out에 저장하고, 재귀를 끝낸다.
3) 선택(append) → 탐색(dfs) → 되돌리기(pop)
for x in range(start, n + 1):
path.append(x) # 선택
dfs(start) # 탐색 (다음 자리로)
path.pop() # 되돌리기
이 3줄이 백트래킹의 뼈대인 듯 하다.
- 선택(append): 후보
x를 현재 수열에 추가한다. - 탐색(dfs): 다음 자리를 계속 채우러 내려간다.
- 되돌리기(pop): 다음 후보를 시도하기 위해 방금 선택을 취소한다.
pop()이 없으면 path가 계속 누적되어서 (이전 선택이 남아있어서) 올바른 탐색 트리가 만들어지지 않는다.
4) 이 문제에서 dfs(start)가 의미하는 것
이 문제는 중복 선택이 허용되기 때문에, 다음 자리에서 선택 범위가 줄어들 필요가 없다.
그래서 재귀 호출이 dfs(x + 1) 같은 형태가 아니라, 계속 dfs(start)를 호출한다.
dfs(start)
즉:
- 매 자리마다
start..n에서 다시 고른다 - 결과적으로
1 1,1 2,2 1,2 2같은 “중복 포함 순열”이 생성된다.
(주의) start 매개변수는 사실 없어도 된다
현재 코드에서는 dfs(1)로 시작하고, 재귀에서도 항상 dfs(start)로 호출하므로, 사실상 start는 항상 1이다.
그래서 아래처럼 더 단순하게 써도 같은 결과가 나온다.
def dfs():
if len(path) == m:
out.append(' '.join(map(str, path)))
return
for x in range(1, n + 1):
path.append(x)
dfs()
path.pop()
다만, N과 M 시리즈의 흐름을 통일하기 위해, start를 남겨두는게 이해에 도움이 되어 그렇게 했다.
이번 문제로 정리한 백트래킹 핵심
- 백트래킹은 “완성 조건” + “선택/탐색/되돌리기” 3단 구조로 이해하면 된다.
- (2)처럼 오름차순/중복 금지 조건이 있으면
start를 다음 단계에 넘겨서 후보 범위를 줄인다. - (3)처럼 중복 허용이면 후보 범위를 줄일 필요가 없어서 매번
1..N을 다시 돈다.