[백준] 15650 N과 M(2) - Python

백트래킹이란?

 

문제 설명에 들어가기 전, 해당 문제는 백트래킹을 사용하는 문제이다. 따라서 백트래킹의 개념에 대해 간단히 짚고 넘어가도록 하자.

 

백트래킹을 간단하게 요약하면, 모든 경우의 수를 살펴가며 Decision Space를 만들고, 가능성이 없는 것들은 탐색을 중지하고 뒤로 돌아가는 방법이다.

 

간단하게 예시를 통해 백트래킹에 대해 알아보자.

 

우리는 일상생활에서 휴대폰을 이용해 전화를 걸 때, 전화기 다이얼을 사용한다. 아래의 다이얼을 살펴보면, 숫자 위에 알파벳들이 나열되어 있는 것을 확인할 수 있다. 

 

 

여기서 알파벳을 이용해 숫자 '25'를 나타내고 싶다고 가정해 보자. '25'를 나타낼 수 있는 모든 알파벳 조합을 나열하면 다음과 같다. [[AJ, AK, AL], [BJ, BK, BL], [CJ, CK, CL]]

 

이 알파벳들을 HashMap으로 변환하면, 우리는 문제에 대한 Decision Space를 다음과 같이 정의할 수 있다.

 

 

먼저, 2를 나타내기 위해서 a,b,c라는 3가지의 decision space를 정의할 수 있다. 다음으로 5를 나타내기 위해 각각의 케이스에 대해 다시 새로운 decision space를 정의할 수 있다. 

 

만약, a가 선택이 되고, 그 다음에 j가 선택이 됐을 경우엔 더 이상 만들어 나갈 decision space가 없으므로 마무리가 되고, 그 옆에 있는 k가 선택이 된다. k 또한 더 이상 만들어 나갈 decision space가 없기 때문에 다음으로 넘어가게 된다. 이 과정을 재귀적으로 수행하며 최종적으로 [[AJ, AK, AL], [BJ, BK, BL], [CJ, CK, CL]]라는 조합을 만들어 낼 수 있는 것이다. 이처럼 만들어 나갈 수 있는 모든 경우의 수를 탐색하며, 더 이상 탐색하지 못할 경우엔 뒤로 돌아가는 방법을 백트래킹이라고 한다.

 

 

문제 설명 & 풀이

 

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

15650번: N과 M (2)

 

 

 

이 문제는 자연수 N과 M이 주어졌을 때, 1부터 N까지의 자연수 중에서 중복 없이 M개를 고른 수열을 오름차순으로 출력하는 간단한 문제이다. 

 

• 입력 1
  • 3 1

 

• 출력 1
  • 1
  • 2
  • 3

 

• 입력 2
  • 4 2

 

• 출력 2
  • 1 2
  • 1 3
  • 1 4
  • 2 3
  • 2 4
  • 3 4

 

 

소스 코드

 

파이썬으로 작성한 코드는 다음과 같다.

import sys
input = sys.stdin.readline

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

result = []
def back_tracking(i):
    if len(result) == m:
        print(' '.join(map(str, result)))
        return
    
    for i in range(i, n+1):
        result.append(i)
        back_tracking(i+1)
        result.pop()

back_tracking(1)

 

 

i부터 n+1 이전까지 백트래킹을 수행하며, result에 i값을 추가한다. i부터 반복문을 진행하는 이유는 출력하고자 하는 수열이 오름차순이어야 하기 때문이다. result에 값을 추가해 나가며 길이가 m일 경우 현재 저장된 값을 출력하고, retrun 하여 pop을 통해 가장 최근에 저장된 값을 제거하고, 다시 반복을 진행한다.