15649. N과 M (1)

문제링크: https://www.acmicpc.net/problem/15649

오랜만에 백준을 들어갔다가, 간단하지만 깊이있는 문제를 만나서 포스팅을 해보겠습니다. 여러가지 mutation이 있는 문제라 오늘은 아마 이 문제에 관한 포스팅만 올라갈것 같습니다.

Problem

문제는 아주 간단합니다. n,m 두 자연수가 주어지고, 1~n 중 m개를 뽑아 만들 수 있는 수열의 리스트를 만들면 됩니다. (1)변형에서는 기본적이게 아무 조건이 붙지 않고 순수하게 초기 조건만 달성하면 됩니다.

Approach & Solution

저는 처음에 간단한 구현&대수 문제라고 생각하고 접근했습니다. 아무래도 말이 '1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열'을 찾는것이라 permutations를 염두해두고 문제를 풀어나갔습니다. 당연히 이것도 맞는 접근이지만, 마지막 (4)변형에서 이 방법으로 풀리지 않아 구글링 하던중, 백트래킹 문제라는 것을 알고 다시 풀어봤습니다.

1. Permutation

import itertools

n, m = map(int,input().split())
target = []
for i in range(1,n+1):
  target.append(i)
data = list(itertools.permutations(target,m))

for i in data:
  print(' '.join(map(str,i)))

순열을 이용한 풀이입니다.

2. DFS & Backtracking

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

result = []
mapping = [False] * (n+1)

def dfs(num):
  if num == m:
    print(' '.join(map(str,result)))
    return
    
  for i in range(1,n+1):
    if mapping[i] != True:
      mapping[i] = True
      result.append(i)
      dfs(num+1)
      result.pop()
      mapping[i] = False

dfs(0)

이해하는데 조금 시간이 걸린 문제입니다.

일단, 백트랙킹이 dfs(깊이우선탐색)의 한 종류라는 것을 알고 가야 합니다. 더 정확하게는, 조건부 dfs인 셈이죠. 따라서 recursion이 당연히 일어나며, 조건에 맞지 않는 경우를 제외하고 탐색을 해야합니다.

코드를 조금 설명하자면,
우선

if num == m:
    print(' '.join(map(str,result)))
    return

num이라는 parameter를 추가하여 깊이를 측정합니다. 깊이가 같을때, 탐색을 종료하고 result에 담긴 값을 출력합니다.

for i in range(1,n+1):
    

그런다음, 반복문을 통하여 root부분이 되는 값을 설정해 줍니다. 당연하게도, 순열의 시작은 1부터 n까지 있을테니까요.

if mapping[i] != True:

그리고 모든 경로를 탐색하는게 아닌, 방문을 했는지 표시 할 수 있는 list도 만들어서 방문을 안한 노드일 경우만 재귀를 실행합니다.

mapping[i] = True
result.append(i)
dfs(num+1)

탐색한 노드는 방문 처리를하고, result에 붙혀줍니다. 그래야 재귀를 들어갔을때 다시 방문하지 않게 말이죠.

result.pop()
mapping[i] = False

탐색이 다 끝났다면, 반복문 안에서 root노드가 다시 사용할 수 있게끔 result에서 값을 지우고, 방문했다는 표시도 false로 만들어 줍니다.

Conclusion

생각보다 많은 지식을 필요로 한 문제였습니다. Recursion, DFS, Backtracking의 컨셉을 모두 이해하고 있어야만, 바로 튀어나올 수 있는 풀이 같아요. Permutation으로도 쉽게 풀 수 있지만, 항상 문제의 의도를 따라가는것이 실력 향상에 가장 도움이 되는것 같습니다. 다음에는 변형문제인 15650. N과 M (2) 을 풀어보겠습니다.