문제
[실버3]
https://www.acmicpc.net/problem/15649
아이디어
N까지의 자연수 중 중복없이 M개를 고른 수열은 곧 순열을 뜻한다.
파이썬에서는 itertools.permutations() 함수를 이용해 답을 구할 수도 있다. (코드 첨부)
하지만 백트래킹을 의도한 문제이기 때문에 이 문제를 백트래킹으로 구현하겠다.
백트래킹
백트래킹(Backtracking)이란 DFS(Depth-First Search, 깊이 우선 탐색)을 기반으로 불필요한 경우를 배제하고 원하는 해답에 도달할 때까지 탐색하는 전략이다.
백트래킹은 DFS 기반이므로 재귀로 구현한다.
백트래킹은 기본적으로 모든 경우의 수를 탐색한다는 브루트 포스(Brute Force) 전략을 취하지만, 처리 속도를 향상시키기 위한 가지치기(Pruning)가 중요한 역할을 한다.
탐색을 하다가, 그 길이 맞지 않으면 왔던 길로 되돌아가 다른 경로로 탐색을 한다.
풀이
이 문제는 반복적으로 숫자를 선택해 M개까지 골라 수열을 완성하는 것이다.
따라서 백트래킹을 적용해 불필요한 경우를 배제한 모든 경우의 수를 고려할 수 있다.
숫자를 선택할 때 1부터 n까지의 자연수 중 선택하므로, 차례대로 선택하는 경우의 수가 있을 수 있다.
이때, 반드시 선택한 숫자를 스택에 추가(Push)하고, 동작(dfs()함수)가 끝난 후에는 다시 스택에서 빼내는 작업(Pop)이 필요하다. 이렇게 함으로써 이전의 상황으로 돌아올 수 있기 때문이다.
for i in range(1, n+1):
s.append(i)
dfs()
s.pop()이렇게 숫자 선택을 반복한 후, 선택한 숫자의 개수가 m이 되면 모두 골랐으므로 답이 된다.
if len(s) == m:
print(' '.join(map(str, s)))
return
for i in range(1, n+1):
if i in s:
continue
s.append(i)
dfs()
s.pop()하지만 위와 같이 항상 1부터 n까지의 자연수를 모두 순회하면, 이미 선택한 숫자를 또 선택하며 시간을 낭비하게 된다. 따라서 이미 선택한 숫자를 다시 선택하려 하면 배제하는 방식으로 가지치기를 할 수 있다.
예를 들어 n = 4, m =2인 경우
첫 자리에 1이 오는 경우, 둘째 자리에는 1을 제외한 나머지 숫자만 올 수 있다.
-> (1,2), (1,3), (1,4) 가능 / (1,1) 불가능
자릿수가 두자리인 경우 이중포문을 이용하면 간단하게 풀 수 있지만 m이 커질수록 반복문을 계속 중첩시킬 수 없기 때문에 백트래킹을 사용해야 한다.
-> 이미 뽑은 숫자인 경우 제외시키면 된다.
if len(s) == m:
print(' '.join(map(str, s)))
return
for i in range(1, n+1):
if i in s:
continue
s.append(i)
dfs()
s.pop()최종 소스코드는 아래와 같다.
n, m = map(int, input().split())
s = []
def dfs():
if len(s) == m:
print(' '.join(map(str, s)))
return
for i in range(1, n+1):
print("i : " + str(i))
if i in s:
continue
s.append(i)
dfs()
s.pop()
dfs()+ 순열을 이용한 풀이
from itertools import permutations
n, m = map(int, input().split())
array = []
for i in range(n):
array.append(i+1)
for p in permutations(array, m):
for i in range(m):
print(p[i], end = " ")
print()Comment
연구소 문제를 풀이하려던 중 백트래킹 개념이 나와 이 문제부터 풀어보게 되었다.
백트래킹 개념은 분명 대충은 알고 있었는데, 오랜만에 접해서 그런가 명확히 개념이 정립된 상태가 아니었고, 문제에 적용했을 때 한번에 이해가 되지 않았다.
앞으로 N과 M 시리즈를 풀이하며 백트래킹 개념을 잘 잡아가고자 한다! 마무리는 연구소 문제로 올리도록 하겠다.
