[파이썬(Python)] 백준 15649번 N과 M (1)

 

 

백준 15649번: N과 M (1)

문제 바로 가기

---

📌 문제

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

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

입력

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

출력

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

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

 

 

 

 

 

 

 

 

 

 

📝 아이디어

 

 

문제 분석

 

자연수 $N$과 $M$이 주어질 때, 1부터 $N$까지의 자연수 중에서 중복 없이 $M$개의 수를 선택하여 수열을 만들어야 합니다. 만들어진 수열은 사전 순(오름차순)으로 한 줄씩 출력해야 합니다. 이 문제에서 중복 없이 M개의 수를 선택하는 과정은 순열(Permutation)을 만드는 과정과 동일합니다.

 

 

 

 

 

문제 조건

 

1. 중복 없는 선택

• 한 번 선택한 숫자는 다시 선택할 수 없습니다.
• 즉, 같은 숫자가 포함된 순열은 허용되지 않습니다.
• 예를 들어 $(1, 2)$를 선택했다면 다시 1을 선택할 수 없습니다.

 

 

2. 순서가 있는 수열

• 숫자의 선택 순서가 다르면 서로 다른 경우로 취급됩니다.
• 예를 들어 $N = 4, M = 2$일 때 $(1, 2)$과 $(2, 1)$은 다른 경우입니다.

 

 

3. 사전 순 출력

• 작은 숫자부터 먼저 선택하여 탐색해야 합니다. 
• 즉 $1, 2, 3, \dots, N$ 순서로 선택하면 자동으로 사전 순 정렬된 결과가 출력됩니다. 

 

 

 

 

 

 

아이디어

 

이 문제를 해결하기 위해 백트래킹 (Backtracking) 기법을 사용합니다. 백트래킹은 가능한 모든 경우를 탐색하면서 조건에 맞지 않는 경우는 조기에 탐색을 중단하는 방식입니다. 즉, 불필요한 연산을 줄이면서 효율적으로 순열을 생성할 수 있습니다. 백트래킹을 구현하는 과정은 다음과 같습니다.

 

 

 

1. 순열 구성

 

1부터 $N$까지의 숫자 중에서 중복 없이 $M$개의 숫자를 선택하여 순열을 만듭니다. $N$개의 숫자 중에서 순서를 고려하며 $M$개를 선택하는 경우이므로 순열 문제로 볼 수 있습니다.

 

 

 

2. 재귀 탐색

현재 선택된 숫자 리스트를 seq라고 할 때

• 만약, seq의 길이가 $M$이 되면 출력하고 종료합니다.
• 그렇지 않다면, 아직 선택하지 않은 숫자를 seq에 추가한 후 재귀 호출을 수행하여 다음 숫자를 선택합니다.

 

 

 

3. 방문 여부 확인

 

중복을 방지하기 위해 visited 배열을 사용합니다.

예를 들어 visited = [False, False, False, False]와 같은 배열을 사용합니다.

• 숫자를 선택하면 해당 인덱스를 True로 변경하여 다시 선택할 수 없도록 합니다.
• 탐색이 끝나면 다시 False로 바꿔 원상 복구합니다.

이렇게 방문 여부를 확인하면 같은 숫자가 중복 선택되지 않습니다.

 

 

 

4. 백트래킹 수행

 

재귀 호출이 끝난 후에는 마지막으로 추가한 숫자를 제거하여 원상 복구합니다. 그리고 다른 숫자를 선택할 수 있도록 탐색을 계속 진행합니다. 이렇게 하면 모든 가능한 경우를 빠짐없이 탐색할 수 있습니다. 

 

 

 

 

 

시간 복잡도 분석

 

모든 경우를 탐색하는 과정이므로 순열의 개수만큼 연산이 발생합니다.

 

$$P(N,M) = \frac{N!}{(N - M)!}$$

 

최대 입력인 $N = 8, M = 8$일 경우 , $P(8, 8) = 8! = 40320$이므로 충분히 가능합니다.

 

 

 

 

 

 

 

 

 

 

👩‍💻 나의 답안

def backtrack(n, m, seq, visited):
    if len(seq) == m:
        print(" ".join(map(str, seq)))
        return 
    
    for i in range(1, n+1):
        if not visited[i]:
            visited[i] = True
            backtrack(n, m, seq + [i], visited)
            visited[i] = False

def solve(n, m):
    visited = [False] * (n + 1)
    backtrack(n, m, [], visited)


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

 

Algorithm/백준/Silver/15649. N과 M （1） at main · kuun1000/Algorithm