Python을 이용한 15649번 : N과 M(1)에 대해서 포스팅하겠습니다.
15649번 문제설명
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
- 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 구해야합니다.
접근방법
- DFS 및 백트래킹 개념 이해: DFS는 탐색을 할 때 하나의 경로를 끝까지 탐색한 후 다른 경로를 탐색하는 방식입니다. 백트래킹은 탐색 과정에서 특정 조건을 만족하지 않을 경우 이전 단계로 돌아가 다른 경로를 탐색하는 방법입니다.
- DFS 구현:
- 함수 정의: DFS를 수행할 함수를 정의합니다. 이 함수는 현재까지 선택된 숫자들의 리스트(수열)를 매개변수로 받습니다.
- 종료 조건: 수열의 길이가
M
에 도달했을 때, 해당 수열을 출력하고 함수를 종료합니다. - 탐색 과정:
1
부터N
까지의 숫자들을 순회하면서, 아직 수열에 포함되지 않은 숫자를 찾아 수열에 추가합니다. - 재귀 호출: 새로운 숫자를 추가한 후, 변경된 수열을 가지고 다시 DFS 함수를 재귀적으로 호출합니다.
- 백트래킹: 재귀 호출이 끝나면, 마지막에 추가한 숫자를 수열에서 제거하여 다른 숫자를 선택할 수 있도록 합니다.
코드 접근 법
코드는 깊이 우선 탐색(DFS)를 이용하여 문제를 해결합니다. 아래는 코드의 주요 부분에 대한 설명입니다:
- 입력 받기:
n
과m
값을 입력받습니다. 여기서n
은 선택할 수 있는 숫자의 범위,m
은 생성할 수열의 길이입니다. - 변수 초기화:
s
: 현재까지 생성된 수열을 저장하는 리스트입니다.result
: 최종적으로 생성된 모든 수열을 저장하는 리스트입니다.
- 깊이 우선 탐색(DFS) 함수
dfs
정의:- 수열
s
의 길이가m
과 같으면,s
를 결과 리스트에 추가합니다. - 1부터
n
까지의 숫자를 순회합니다. 순회하는 숫자가s
에 없으면, 즉 아직 방문하지 않은 숫자라면s
에 추가하고dfs
를 재귀적으로 호출합니다. - 호출이 끝나면
s
에서 마지막 요소를 제거합니다. 이는 다른 수열을 생성하기 위한 준비 과정입니다.
- 수열
- 수열 생성 시작:
dfs
함수를 호출하여 수열 생성을 시작합니다. - 결과 출력: 생성된 모든 수열을 출력합니다.
15649번 코드
Python
#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))