[Python | 15649] N과 M (1)

Algorithm/Baekjoon

[Python | 15649] N과 M (1)

dotz0ver 2025. 3. 3. 19:13

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

문제 설명

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

📌 시간 제한: 1초

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

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

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

문제 접근

완전 탐색이 가능한지?

이 문제는 1부터 N까지의 숫자 중 중복 없이 M개를 선택하는 경우를 모두 찾아야 한다. 하지만 단순한 반복문으로는 해결하기 어렵다. 그 이유는 N과 M의 값에 따라 루프의 깊이가 달라지기 때문에, 고정된 반복문으로 처리할 수 없기 때문이다.

이 문제의 핵심은 순서가 중요한 "순열(Permutation)" 문제라는 점이다. 즉, 같은 숫자 조합이라도 순서가 다르면 다른 경우로 취급해야 한다. 예를 들어, [1,2]와 [2,1]은 서로 다른 경우로 간주된다.

그렇다면 모든 경우를 강제로 확인하는 브루트포스(Brute Force) 방식을 생각할 수 있지만, 이 역시 비효율적이다. 경우의 수가 많아질수록 불필요한 탐색이 증가하며, 특히 선택된 숫자를 다시 선택하지 않도록 관리해야 하는 문제가 발생한다. 따라서 탐색 과정에서 유망하지 않은 경로는 미리 제외하여 연산량을 줄이는 방법이 필요하다.

이러한 이유로 백트래킹(Backtracking) 기법을 활용한다. 백트래킹은 브루트포스를 기반으로 하지만, 불필요한 탐색을 줄이기 위해 가지치기(Pruning) 기법을 적용할 수 있다.

✅ 백트래킹이란?

가능한 모든 경우를 탐색하지만, 유망하지 않은 경로는 미리 탐색하지 않고 제외하여 연산량을 줄이는 기법이다.

이 문제에서 이미 선택한 숫자는 다시 선택할 필요가 없으므로 탐색에서 제외하는 것으로 가지치기를 적용할 수 있다.

백트래킹을 구현할 때는 보통 DFS(Depth-First Search, 깊이 우선 탐색) 방식을 사용한다.
DFS 방식은 한 방향으로 가능한 만큼 깊이 탐색한 후, 다시 돌아가서 다른 경로를 탐색하는 방식이다. (백트래킹이 반드시 DFS만을 사용해야 하는 것은 아님)

DFS는 재귀 방식과 반복문(스택) 방식으로 구현할 수 있지만, 이 문제에서는 선택 과정이 반복적으로 진행되므로 재귀를 사용하는 방식이 적절하다.

재귀로 풀 수 있는지?

현재 숫자를 선택하면, 남은 숫자 중에서 하나를 골라 다시 같은 과정을 수행해야 한다. 이러한 구조는 자연스럽게 재귀 호출 형태로 이어지며, 각 단계에서 선택한 숫자를 제외하고 다음 탐색을 진행할 수 있도록 한다.

예를 들어, N=3, M=2일 때 가능한 경우를 나열하면 다음과 같다.

이 과정을 백트래킹 탐색 트리로 나타내면 다음과 같다.

backtrack(0)   # 시작
 ├── 1 선택 → backtrack(1)  # 깊이 증가 (DFS)
 │     ├── 2 선택 → backtrack(2) → [1 2] 출력 → 돌아감 (백트래킹)
 │     ├── 3 선택 → backtrack(2) → [1 3] 출력 → 돌아감 (백트래킹)
 │
 ├── 2 선택 → backtrack(1)
 │     ├── 1 선택 → backtrack(2) → [2 1] 출력 → 돌아감 (백트래킹)
 │     ├── 3 선택 → backtrack(2) → [2 3] 출력 → 돌아감 (백트래킹)
 │
 ├── 3 선택 → backtrack(1)
       ├── 1 선택 → backtrack(2) → [3 1] 출력 → 돌아감 (백트래킹)
       ├── 2 선택 → backtrack(2) → [3 2] 출력 → 돌아감 (백트래킹)

탐색 조건 정리

현재까지 선택한 숫자들을 저장하고, 길이가 M이 되면 출력
이미 선택된 숫자는 다시 선택하면 안 됨
선택되지 않은 숫자들 중에서 선택해 다음 단계로 넘어감

📌 시간 복잡도 분석

이 문제에서 탐색의 깊이는 M이며, 한 단계에서 선택할 수 있는 숫자는 N에서 점점 줄어든다.
따라서 가능한 탐색 경로의 수는 다음과 같다.
N × (N-1) × (N-2) × ... × (N-M+1) = P(N, M)  (순열, Permutation)
즉, 최악의 경우 O(N!)의 시간 복잡도를 가진다.
일반적으로 N > 10~12 정도로 크면 연산량이 너무 많아 최적화가 필요하지만,이 문제에서는 입력 조건이 다음과 같다.
1 ≤ M ≤ N ≤ 8
이를 고려했을 때, 최대 연산량은 O(8!) = 40,320이므로 1초 동안 약 10^7번의 연산이 가능한 코딩 테스트 환경에서는 충분히 해결할 수 있다.

구현

코드 1 : 백트래킹

숫자 선택 & 방문 체크
- 1부터 N까지의 숫자를 선택하는 for문을 사용한다.
- visited 배열을 활용해 중복 여부를 체크한다.
- visited는 1부터 N까지 사용하기 때문에 크기를 N+1로 설정해야 한다.
재귀 호출 & 탐색 진행
- 방문하지 않은 숫자라면 배열에 추가한 후, 재귀 호출을 통해 다음 숫자를 선택한다.
- 재귀 호출이 끝나면 다른 숫자와 조합을 만들기 위해 백트래킹을 수행하여 원래 상태로 복구한다.
- 이 과정에서 가지치기(Pruning) 기법을 적용하여 중복된 탐색을 방지할 수 있다.
- 이번 문제에서는 이미 선택된 숫자는 다시 선택하지 않는 것이 가지치기에 해당한다.
재귀 종료 조건
- M개의 숫자를 모두 선택한 경우, 즉 arr의 길이가 M이 되면 탐색을 종료하고 결과를 출력한다.
백트래킹 처리
- 방문했던 숫자를 다시 선택할 수 있도록 백트래킹 시 visited 값을 원래대로 복구한다.

n, m = map(int, input().split())
visited = [False] * (n + 1)
arr = []

def dfs():
    if len(arr) == m:
        print(*arr)
        return

    for i in range(1, n+1):
        if not visited[i]: # 방문하지 않았다면 선택
            visited[i] = True
            arr.append(i)
            dfs()
            arr.pop() # 백트래킹
            visited[i] = False # 방문 해제

dfs()

코드 2 : itertools.permutations

Python에서는 itertools.permutations을 사용하면 더 간단하게 순열을 구할 수도 있다.

from itertools import permutations

n, m = map(int, input().split())

for perm in permutations(range(1, n+1), m):
    print(*perm)