[Algorithm] 1일1솔 - 백준 15649 N과 M (1) (python3)

문제링크

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

15649번: N과 M (1)

문제설명

자연수 N과 M이 주어졌을 때, '1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열' 조건을 만족하는 길이가 M인 수열을 모두 구하는 문제이다.

문제 분류는 백트래킹으로 되어있지만, 중복 없이 일정한 개수의 자연수가 담긴 수열을 구하며, 순서를 상관하여 수열을 다르게 취급한다는 점에서 순열을 이용해서 풀이할 수도 있다.

문제풀이

1. 순열

이 문제에서는 수열을 순서가 다르면 다른 수열로 취급하고 있기 때문에 순열로 풀이할 수 있다.

가장 먼저 떠오른 풀이가 순열로 푸는 것이었기에 itertools 의 permutations 를 활용해서 풀었다. 시간은 백트래킹 알고리즘보다 덜 소요되었다.

import sys
from itertools import permutations

n, m = map(int, sys.stdin.readline().split())
permute = permutations(range(1,n+1),m)
for x in permute:
    print(*x)

 

2. 백트래킹 알고리즘

문제의 본래 출제 의도인 백트래킹으로 풀이하였다. DFS로 탐색을 하며 백트래킹을 취해 pruning 작업을 수행했다.

백트래킹(Backtracking, 퇴각검색) 이란?

DFS(Depth-First Search, 깊이 우선 탐색)의 방식을 기반으로 스택(stack)을 이용해 불필요한 경우를 배제하며(=퇴각을 하며) 원하는 해답에 도달할 때까지 탐색하는 전략이다.

기본적으로 모든 경우의 탐색하는 브루트 포스(Brute Force) 전략을 취하지만, 처리 속도를 향상시키기 위한 가지치기(Pruning)가 중요한 역할을 한다.

 

이 문제는 숫자를 선택하는 경우의 수로 이루어진 트리로 볼 수 있으며, 반복적으로 M개까지 숫자를 선택해 수열을 만드는 것이 목표이다. 따라서 재귀를 활용한 DFS를 활용해야 함을 알 수 있으며, 효율적인 풀이를 위해 백트래킹을 적용하여 불필요한 경우는 배제하고 필요한 경우만 고려할 수 있다.

 

여기서는 차례로 경우의 수를 구해야하므로, 스택에 수를 추가(append)해준 후, 탐색 작업(dfs 함수)이 끝난 후에는 다시 스택에서 제거(pop)하는 작업이 필요하다.

해당 과정은 1부터 N까지의 자연수 i 를 for 문으로 차례로 돌면서 이루어지도록 했으며, 이때 pruning을 하여 자연수 i 가 스택에 없는 경우만 고려했다.

또한, M만큼의 길이의 수열마다 출력을 해야하므로 탈출 조건은 스택의 길이가 M이 될 때로 설정했다.

import sys
n, m = map(int, sys.stdin.readline().split())
ret = []  # 스택

def dfs():
    if len(ret) == m:   # 탈출 조건(ret 길이가 m 되면 출력)
        print(*ret)
        return
    for i in range(1,n+1):
        if i not in ret:   # 가지치기(pruning) 작업
            ret.append(i)
            dfs()
            ret.pop()
dfs()

 

 

그리고 백트래킹 알고리즘을 공부하며 백트래킹과 브루트포스, DFS의 관계가 다소 헷갈려 그 개념을 정리해보았다.

백트래킹 vs DFS

• DFS : 여러 지점을 한 단계씩 거치며 탐색하고 스택의 개념을 이용해서 이전 단계로 돌아가는 알고리즘
• 백트래킹 : 이미 지나쳐온 곳을 다시 돌아가서 다른 가능성을 시도해보는 걸 반복하는 방법론으로, DFS 뿐 아니라 BFS 등으로도 가능한 기법

   백트래킹은 하나의 문제 해결 방법론이고, 이러한 백트래킹을 구현하는 방법 중 하나가 DFS이다.

백트래킹 vs 브루트포스

• 브루트포스 : 모든 경우의 수를 탐색하는 문제 해결 방법론
• 백트래킹 : 단계마다 조건을 충족하는지 검사하여 조건을 충족하는 경우에만 계속해서 탐색하는 문제 해결 방법론

   브루트포스는 모든 가지를 탐색하는 방법론이고, 백트래킹은 조건을 보고 가지치기를 해나가면서 탐색하는 방법론이다.

백트래킹 vs 브루트포스 vs DFS

• 백트래킹 : 이미 지나쳐온 곳들 다시 돌아가서 다른 가능성을 시도해보는 걸 반복하는 기법. DFS 뿐 아니라 BFS 등으로도 가능하지만, 일반적으로 DFS와 연관이 깊다.
• 브루트포스 : 꼭 '깊이'나 '탐색'의 개념이 아니더라도, 문제의 종류나 기법과 무관하게 모든 경우의 수를 다 대입해보는 방식.
• DFS : 여러 지점을 한 단계씩 거쳐가면서 탐색하고, 스택의 개념을 이용해서 이전 단계로 돌아가는 알고리즘.

---

References

https://www.youtube.com/watch?v=HRwFgtiqHH0 

https://www.acmicpc.net/board/view/20320

https://www.youtube.com/watch?v=HRwFgtiqHH0 

https://jamesu.dev/posts/2020/04/13/baekjoon-problem-solving-15649/

백트래킹 vs DFS vs 브루트포스