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

문제 링크

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

문제

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

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

입력

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

출력

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

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

예제

입력

4 2

출력

1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3

---

정답 및 풀이

import sys
input = sys.stdin.readline

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

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

    for i in range(1, n + 1):
        if not visited[i]:
            visited[i] = True
            result.append(i)
            dfs()
            result.pop()
            visited[i] = False

dfs()

1. n, m = map(int, input().split())
   • 1부터 n까지의 수 중에서 길이가 m인 수열을 만들기 위한 입력값
2. visited = [False] * (n + 1)
   • 숫자의 중복 사용을 막기 위한 방문 체크 배열
   • 인덱스를 숫자 그대로 사용하기 위해 n+1 크기
3. result = []
   • 현재 선택된 숫자들을 저장하는 리스트 (수열)
4. def dfs():
   • 백트래킹(DFS) 방식으로 모든 경우의 수를 탐색하는 함수
5. if len(result) == m:
   • 수열의 길이가 m이 되면 하나의 완성된 경우
6. print(*result)
   • 리스트를 공백 기준으로 출력
7. for i in range(1, n + 1):
   • 1부터 n까지 모든 숫자를 순회하며 선택 시도
8. if not visited[i]:
   • 아직 사용하지 않은 숫자인 경우만 선택
9. visited[i] = True
   • 숫자 i를 사용했다고 표시
10. result.append(i)
    • 현재 수열에 숫자 i 추가
11. dfs()
    • 다음 자리 숫자를 선택하기 위해 재귀 호출
12. result.pop()
    • 이전 상태로 되돌리기 (백트래킹 핵심)
13. visited[i] = False
    • 숫자 i를 다시 사용할 수 있도록 방문 해제
14. dfs()
    • 탐색 시작

---

새롭게 배운 내용 및 느낀점

• 백트래킹 (Backtracking)
  • 모든 경우의 수를 탐색하되, 조건에 맞지 않으면 되돌아감
• DFS (Depth First Search)
  • 깊이 우선 탐색 방식으로 수열을 하나씩 완성해 나감
• visited 배열
  • 같은 숫자가 중복해서 사용되지 않도록 관리