[Python/파이썬] 백준 알고리즘 15649번 - N과 M (1) (BackTracking)

 

 

 

<풀이>

1. 아이디어
for문으로 1부터 N까지 돌리면서 이미 선택한 값이 아닌 경우 선택
M개 선택하는 경우 출력하고 return
하나의 리스트를 사용할 것이고 return해서 위 depth로 올라왔을 때 그대로 append만 하면
기존 리스트의 옆에 붙을테니 백트래킹 방식으로 return할 때 리스트 맨 끝을 지워주는 처리를 해줘야함.

2. 시간복잡도
- BackTracking
- 중복이 가능한 경우 : O(N^N)   (N = 8까지 가능)    (시간제한 1초인데 1초에 2억까지 처리가능하므로)
- 중복이 불가능한 경우 : O(N!)   (N = 10까지 가능)
- 중복이 불가능하면 depth가 깊어짐에 따라 N개에서 하나씩 줄어드니까 N!인 것

3. 자료구조
N, M: int;
result = int[];
visited = bool[];

 

전체 코드 ↓

import sys
sys.setrecursionlimit(10 ** 6)  # 재귀 사용 시 필수! 재귀 깊이 제한 늘려서 런타임에러 없애기 용

input = sys.stdin.readline

N, M = map(int, input().split())
result = []
visited = [False] * (N + 1)


def backTracking(num):
    if num == M:
        print(' '.join(map(str, result)))
        return
    for i in range(1, N + 1):
        if not visited[i]:
            visited[i] = True
            result.append(i)
            backTracking(num + 1)
            visited[i] = False
            result.pop()


backTracking(0)

 

뜯어서 보겠다.

N, M = map(int, input().split())
result = []
visited = [False] * (N + 1)

result는 출력할 숫자들을 받아주는 리스트다. 여기 안의 원소수가 M이되면 출력해주도록 할 것이다.

visited는 방문했는지를 체크하는 리스트이다. 편의상 인덱스 1부터 사용할 것이며 따라서 N+1을 곱했다.

중복을 허용하지 않는다 했기때문에 방문했는지를 체크하는 리스트가 필요했다.

 

def backTracking(num):
    if num == M:
        print(' '.join(map(str, result)))
        return
    for i in range(1, N + 1):
        if not visited[i]:
            visited[i] = True
            result.append(i)
            backTracking(num + 1)
            visited[i] = False
            result.pop()

백트래킹 함수이다.

백트래킹은 알고리즘 수업에서 배웠다시피 DFS의 향상된 버전이다. 즉, 기본은 DFS이지만 조금 다른 부분이 있다는 것이다.

num을 사용하지 않고 if문에서 len()함수를 사용해서 len(result)로 해도 되지만 알고리즘을 이해하는 측면에서 num을 사용하는게 좋다. num은 트리의 depth를 표현한다고 생각하면 된다.

보면 기본 구조는 DFS와 같다. if문으로 return하는 부분을 처리하고 그때 print한다.

그리고 for문으로 같은 depth의 노드들을 순회한다. for문안에서 함수가 다시 호출되기 때문에 DFS 방식으로 순회된다.

visited[i] = True
result.append(i)
backTracking(num + 1)
visited[i] = False
result.pop()

백트래킹의 특징은 위 부분이다.

backTracking(num+1)로 함수가 호출되는 코드라인을 기준으로 위에서는 visited[i]를 True로 해주고 result리스트에 i를 append해준다.

그리고 backTracking(num+1) 함수를 마치고 빠져나오면 다시 visited[i]를 False로 해주고 result리스트에서 방금들어갔던 i값을 pop해준다.

이걸 그림을 보며 생각해보면 아래와 같다.

dfs방식으로 순회하면서 위 번호와 같이 순회한다고 할 때, 2 -> 3 으로 갔다가 다시 2로 올라올 때

visited[i] = False
result.pop()

가 필요한 것이다.

 

---

 

또 다른 풀이 ↓

# 다른 풀이 ↓
def backTracking2(num):
    if num == M:
        print(' '.join(map(str, result)))
        return
    for i in range(1, N + 1):
        if i not in result:     # in연산자를 사용하면 visited 리스트 없이도 구현가능
            result.append(i)    # 하지만 O(n)만큼 더 순회하므로 시간복잡도 면에서는 visited를 사용하는게 좋다.
            backTracking2(num + 1)
            result.pop()

다른 풀이다. 다 똑같은데 visited 리스트를 사용하지 않는다는 차이점이 있다.

위와 같이 if문에서 파이썬의 in 연산자를 사용하면 visited 리스트도 사용하지 않고 더 간결한 코드로 구현할 수 있다.

하지만 in 연산자는 O(n)의 시간복잡도를 갖기에 시간복잡도면에서는 visited 리스트를 사용하는 것이 좋을 것이다.

공간 복잡도면에서는 위 코드가 낫다.

 

백트래킹은 DFS를 충분히 공부했다면 수월하게 이해할 수 있는 부분인 것 같다.

DFS를 더 단단히 다져야겠다.

 

 

 

<핵심 정리>

1. 백트래킹은 DFS의 Implement이다.

2. 함수가 호출되고 나온 이후 부분에 원상복구해주는 코드가 필요하다.

3. 백트래킹을 사용할 때 파라매터를 depth로 생각하고 구현하면 구현에 용이하다.

4. 파이썬 in연산자의 시간복잡도는 O(n)이다.