[백준 Python] 15651번. N과 M (3) (백트래킹)

728x90

15651번. N과 M (3) - 백트래킹

1. 문제

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

2. 풀이

이 문제는 백트래킹을 이용해 모든 경우의 수를 구하는 문제이다.

여기서는 res라는 리스트를 사용해 수열을 담는다.

간단하게 말하면,
1부터 n까지 차례대로 res에 append하는데
수열(res)의 길이가 m이 되면 출력하고, 다시 돌아간다.
그리고 마지막 원소를 pop해서 뺀다.

📌 코드 설명

입력 받기:
```
n, m = map(int, input().rstrip().split())
```
n: 1부터 n까지의 숫자를 사용한다.
m: 만들어야 하는 수열의 길이.

백트래킹 함수 정의:
```
def backtrack(res):
```

이 함수는 res라는 리스트를 인자로 받아, 수열을 계속해서 완성해 나간다.
재귀 호출을 이용해 모든 가능한 수열을 탐색한다.

수열 완성 조건:

if len(res) == m:
 print(' '.join(map(str, res)))
 return

res의 길이가 m이 되면, 하나의 수열이 완성된 상태다.
이때 수열을 출력하고 함수를 종료한다.

여기서 res는 int 배열이기 때문에, 그냥 join하려고 하면 오류가 발생한다.
따라서 map(str, res) 해서 join해야 한다.

수열 생성 과정:

for i in range(1, n+1):
 res.append(i)
 backtrack(res)
 res.pop()

1부터 n까지의 모든 숫자를 시도한다.
각 숫자를 res에 추가하고 (append()),
다시 backtrack() 함수를 호출해 다음 숫자를 추가하는 과정을 반복한다.
재귀 호출이 끝나면 마지막 원소를 제거 (pop()) 하여 이전 상태로 돌아간다.
- 이렇게 해야 다른 수열을 만들 수 있기 때문이다.

💡 핵심 포인트

모든 경우의 수를 구하기 위해 재귀 호출 사용.
DFS (깊이 우선 탐색) 방식으로 모든 가능한 수열을 만들어냄.
백트래킹의 핵심은 정답을 찾으면 이전 상태로 돌아가서 다른 경우를 탐색하는 것이다.

3. CODE

import sys
input = sys.stdin.readline

n, m = map(int, input().rstrip().split())
res = []

# 백트래킹
def backtrack(res):
    if len(res) == m:
        print(' '.join(map(str, res)))
        return
    else:
        for i in range(1, n+1):
            res.append(i)
            backtrack(res)
            res.pop()

backtrack(res)

결과