백준 15649번: N과 M (1)  – Python(파이썬)

Python을 이용한 15649번 : N과 M(1)에 대해서 포스팅하겠습니다.

15649번 문제설명

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

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 구해야합니다.

접근방법

1. DFS 및 백트래킹 개념 이해: DFS는 탐색을 할 때 하나의 경로를 끝까지 탐색한 후 다른 경로를 탐색하는 방식입니다. 백트래킹은 탐색 과정에서 특정 조건을 만족하지 않을 경우 이전 단계로 돌아가 다른 경로를 탐색하는 방법입니다.
2. DFS 구현:
   • 함수 정의: DFS를 수행할 함수를 정의합니다. 이 함수는 현재까지 선택된 숫자들의 리스트(수열)를 매개변수로 받습니다.
   • 종료 조건: 수열의 길이가 M에 도달했을 때, 해당 수열을 출력하고 함수를 종료합니다.
   • 탐색 과정: 1부터 N까지의 숫자들을 순회하면서, 아직 수열에 포함되지 않은 숫자를 찾아 수열에 추가합니다.
   • 재귀 호출: 새로운 숫자를 추가한 후, 변경된 수열을 가지고 다시 DFS 함수를 재귀적으로 호출합니다.
   • 백트래킹: 재귀 호출이 끝나면, 마지막에 추가한 숫자를 수열에서 제거하여 다른 숫자를 선택할 수 있도록 합니다.

코드 접근 법

코드는 깊이 우선 탐색(DFS)를 이용하여 문제를 해결합니다. 아래는 코드의 주요 부분에 대한 설명입니다:

1. 입력 받기: n과 m 값을 입력받습니다. 여기서 n은 선택할 수 있는 숫자의 범위, m은 생성할 수열의 길이입니다.
2. 변수 초기화:
   • s: 현재까지 생성된 수열을 저장하는 리스트입니다.
   • result: 최종적으로 생성된 모든 수열을 저장하는 리스트입니다.
3. 깊이 우선 탐색(DFS) 함수 dfs 정의:
   • 수열 s의 길이가 m과 같으면, s를 결과 리스트에 추가합니다.
   • 1부터 n까지의 숫자를 순회합니다. 순회하는 숫자가 s에 없으면, 즉 아직 방문하지 않은 숫자라면 s에 추가하고 dfs를 재귀적으로 호출합니다.
   • 호출이 끝나면 s에서 마지막 요소를 제거합니다. 이는 다른 수열을 생성하기 위한 준비 과정입니다.
4. 수열 생성 시작: dfs 함수를 호출하여 수열 생성을 시작합니다.
5. 결과 출력: 생성된 모든 수열을 출력합니다.

15649번 코드

#https://www.acmicpc.net/problem/15649
# n과 m을 입력받습니다.
n, m = list(map(int, input().split())) 

# s는 현재까지 생성된 수열을 저장합니다.
s = []

# result는 최종적으로 생성된 모든 수열을 저장합니다.
result = []

# 깊이 우선 탐색(DFS) 함수를 정의합니다.
def dfs():
    # 만약 s의 길이가 m과 같다면, s를 결과에 추가합니다.
    if len(s) == m:
        result.append(" ".join(map(str, s)))
        return
    
    # 1부터 n까지의 숫자를 순회합니다.
    for i in range(1, n + 1):
        # 만약 i가 s에 없다면, 즉 아직 방문하지 않았다면
        if i not in s:
            s.append(i) # s에 i를 추가합니다.
            dfs()       # 새로운 수열을 생성하기 위해 dfs를 재귀 호출합니다.
            s.pop()     # s에서 마지막 요소를 제거하여 다른 수열을 생성할 준비를 합니다.

# 깊이 우선 탐색을 시작합니다.
dfs()

# 생성된 모든 수열을 출력합니다.
print("\n".join(result))