백준 N과 M (1) ~ (8) / 파이썬 백트래킹

문제번호	문제이름
15649	N과 M (1)
15650	N과 M (2)
15651	N과 M (3)
15652	N과 M (4)
15654	N과 M (5)
15655	N과 M (6)
15656	N과 M (7)
15657	N과 M (8)
15663	N과 M (9)
15664	N과 M (10)
15665	N과 M (11)
15666	N과 M (12)

백준 N과 M 파이썬 백트레킹 풀이

먼저, Backtracking 기법은 완전 탐색과 비슷하다. 즉 문제풀이에 가능한 모든 경우의 수를 고려하는 풀이법이다.

다만 한가지 더 추가하자면, 일반적으로는 어떠한 '조건'을 만족하는 경우의 수를 구할때 이 용어를 사용한다.

그러므로 일반적으로 모든 경우의 수를 구하는것보다 빠른데 그 이유는, 단순히 모든 경우를 구하는것이 아니라 조건에 맞지않는경우는 배제하기 때문이다.

 

사실, 무슨 말인지 정확히 아는것은 크게 중요하지 않은 것 같다. 나도 용어에 대한 정확한 의미는 몰랐지만 위 문제들은 다 풀어냈으니말이다.

 

우선 N과M 문제를 크게 2개로 분류하자면 1~8번 / 9~12번으로 나눌 수 있다.

1번을 풀 수 있다면 응용해서 8번까지는 무리가 없다.

다만 9번문제는 이전과다른 조건이 추가되므로 풀이를위해서 별다른 장치를 도입해야한다.

N과 M (1) 문제

www.acmicpc.net/problem/15649

15649번: N과 M (1)

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

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

쉽게말해서, Permutation을 구하는 것과 같다.

어떤 수 배열이 주어졌을때 m개의 순열을 구하라는 의미인데, 모든 경우의 수를 찾아보고 만족하는 결과들만 출력해주면 된다.

 

그럼 모든 경우를 탐색해야하는데 N과M 모든 문제를 푸는데 중요한 뼈대는 다음과 같다.

수 배열 = arr, 순열배열 = ary 라 하자

def ccc(arr) :
  ...
  for i in range(len(arr)):
          if arr[i] not in ary:
              ary.append(arr[i])
              ccc(ary)
              ary.pop()

위 코드를 잘 보면, 순열 배열에 추가 -> 재귀 -> 순열 배열에서 제거 와 같은 방식으로 구성되어있다.

이것을 손으로 직접 작동방식을 그려보면 잘 이해할 수 있는데, 위의 코드로 모든 경우를 탐색할 수 있다.

 

그리고 조건이 걸려있는데, 주어진 수가 내 순열 배열에 없는 경우만 계산을 하도록 되어있다. 이는 문제 조건에 따라 중복을 방지하기 위함이다.

import sys
input = sys.stdin.readline

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

arr = [i for i in range(1,n+1)]

def ccc(ary):
    if len(ary) == m :
        for i in ary:
            print(i, end = ' ')
        print()
        return
    
    for i in range(len(arr)):
        if arr[i] not in ary:
            ary.append(arr[i])
            ccc(ary)
            ary.pop()

ccc([])

전체 코드는 위와같다.

이 코드내에서 아까 구성했던 반복문 부분만 응용하면 8번까지 풀이가 가능하다.