백준 15649 문제 분석 python

🐒 N과 M(1)

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

✍ 나의 풀이

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):
        if i in s:
            continue
        s.append(i)
        dfs()
        s.pop()

dfs()

백트래킹 알고리즘은 처음 접해보는 유형이었다.
그래서 구글링을 통해 답안을 살펴보았다.

---

🧠 문제 이해

백트래킹은 무엇일까?

모든 경우의 수를 전부 고려하는 알고리즘 상태공간을 트리로 나타낼 수 있을 때 적합한 방식이다. 일종의 트리 탐색 알고리즘이라고 봐도 된다. 방식에 따라서 깊이우선탐색(Depth First Search, DFS)과 너비우선탐색(Breadth First Search, BFS), 최선 우선 탐색(Best First Search/HeuristicSearch)이 있다. 모든 경우의 수를 고려해야 하는 문제라면, DFS가 낫다. BFS로도 구현이 물론 가능하지만, BFS로 구현했다간 큐의 크기가 . 심지어 속도도 똑같다. 따라서 경우의 수 구하기는 일반적으로 DFS가 편리하다. 대다수의 문제들은DFS를 써도 일단 답은 나온다. - 나무 위키 -

DFS 알고리즘을 이용하여 탐색을 진행하다가 조건에 맞지않는 노드가 등장하면 그 하위 노드들은 스킵하고 다음 요소를 탐색한다

백트래킹은 위와 같이 "가지치기" 를 통해 시간복잡도를 줄일 수 있다.

s = []

def dfs():
    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()

위 코드에

입력
4 2

하면

0. dfs()
1. if len(s) == M: false
2. s.append(1)
3. dfs()
4. if len(s) == M : false
5. if 1 in s: True => continue
6. s.append(2)
7. dfs()
8. if len(s) == M : True
9. print(' '.join(map(str, s)))
10. 7단계 dfs() return
    7-1. s.pop()
    7-2. if 2 in s: false
    7-3. s.append(2)
    7-4. dfs()
    7-5. if len(s) == M : True
    ...

이런식으로 s 배열에 숫자가 들어왔다 출력했다 나갔다 하면서 출력물을 만들어 낸다.

출력
1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3