BOJ(백준) 15649번 N과 M (1) 파이썬

15649번: N과 M (1)

---

코드

import sys
r=sys.stdin.readline
N,M = map(int, r().split())

num=[i+1 for i in range(N)]
check=[False]*N

res=[]

def dfs(cnt):
    if(cnt==M):
        print(*res)
        return

    for i in range(0, N):
        if(check[i]):
            continue

        check[i] = True
        res.append(num[i])
        dfs(cnt + 1)
        res.pop()
        check[i] = False

dfs(0)

 

해설

사실 이 문제는 파이썬 itertools 의 permutations 를 이용해서 쉽게 풀 수 있는 문제이다. 하지만 그렇게 풀어버리면 Backtracking을 활용해 해결해고자 하는 문제의 의도와 다르기 때문에 제출은 해봤지만 여기서 따로 설명하지는 않겠다.

Backtracking을 위키피디아에 검색해보면 한국어로 퇴각검색이라고 뜨며 정의는 다음과 같다.

한정 조건을 가진 문제를 풀려는 전략이다.

사실 처음에 이 문장을 보고 Backtracking이 어떤 알고리즘인지 쉽게 감이 잡히지 않아 다른 분들의 블로그를 참고해 이해보려고 노력하였다. 좋은 설명들이 많아서 이해할 수 있게 되었다. 이해한 내용을 간략하게 요약해보면 DFS를 기반으로 탐색을 하는데 문제의 조건에 맞지 않으면(자식 노드가 유망하지 않으면) 그 상황에서는 더 이상 탐색을 하지 않고 문제를 해결할 때 까지 탐색하는 알고리즘이다.

글로 이해하는 것보다 직접 DFS 그래프를 그려 이해하는게 더 좋은 방법일 것 같아서 위의 문제에서 N=4, M=3인 경우를 가정하여 그래프를 다음과 같이 그려보았다.

1에서 시작했기 때문에 1은 더 이상 올 수 없어 유망하지 않은 자식 노드로 표기하였다. 반면 2, 3, 4는 아직 사용하지 않았기 때문에 모두 유망한 노드들이다. 위의 문제에서는 특정 숫자에 대한 사용 여부를 check 리스트의 False 와 True 를 이용해 구분하였다.

1, 2를 뽑았기 때문에 이제 1, 2는 더 이상 올 수 없는 상황이고 3, 4만 유망한 노드들이다.

1, 2, 3, 4 에서 중복없이 3개를 고르는 수열을 찾는 문제이므로 이 경우 최종적으로 [1, 2, 3]과 [1, 2, 4]가 가능하다.

위의 코드는 이러한 과정을 DFS과 재귀를 이용해 구현한 코드이다. 사실 재귀를 이용해 코드를 작성해본 경험이 거의 없어 다른분들 풀이를 참고하면서 코드를 작성하였다. 이를 바탕으로 나머지 N과 M 문제 시리즈들은 혼자 처음부터 끝까지 작성하는 시도를 해봐야 할 것 같다.

 

결과

---

Reference

• 알고리즘 되추적(Backtracking)을 알아보자