[백준] 2098번 외판원 순회 _ Python

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

2098번: 외판원 순회

 

 

---

 

1. Preview

시간 복잡도 : O(N^2 * 2^N)

      N * 2^N : 비트마스킹과 각 노드에 대한 연산 (=현재 위치한 도시의 수 * 방문 도시의 경우의 수)

      N : 다음 도시 경우의 수

공간 복잡도 : O(N * 2^N)

 

참고

- https://withhamit.tistory.com/246 (이론)

- https://velog.io/@dltmdrl1244/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%99%B8%ED%8C%90%EC%9B%90-%EC%88%9C%ED%9A%8CTSP-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98 (dp 배열을 INF로 초기화 한 코드, 틀림)

- https://velog.io/@jxlhe46/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%99%B8%ED%8C%90%EC%9B%90-%EC%88%9C%ED%9A%8C-%EB%AC%B8%EC%A0%9C (올바르게 푼 코드)

- https://programmer-hoo.tistory.com/59 (55% 시간초과 해결)

 

 

---

 

2. 초기 접근 방법

TSP 알고리즘 : 임의의 도시에서 출발해서 모든 도시를 돌고, 다시 출발지로 돌아왔을 때 최소 비용

사이클이 발생하기 때문에, 출발지를 어디로 하더라도 모든 도시를 돌아서 다시 출발지로 돌아오는데 드는 최소 비용은 같다.

 

https://withhamit.tistory.com/246

 

 

1번 그림은 1 → 2 → 3 → 5 → 4 → 1

2번 그림은 1 → 3 → 2 → 5 → 4 → 1 의 경로를 가진다.

 

이 때 5 → 4 → 1 의 경로를 중복 탐색하므로 메모제이션을 사용할 수 있다.

 

dp 배열 정의와 점화식을 세워보면 다음과 같다.

- dp[i][j] = k

       i : 현재 위치한 도시 번호

       j : 지금까지 방문한 도시들의 정보

       k : 남은 도시들을 최소 거리로 돌았을 때의 비용

 

- 점화식

       dp[i][j] = min(dp[i][j], dp[i][k] + temp)

       temp :  dfs(i, visited | (1<<i))

                      k 도시에서 방문하지 않는 도시들을 방문했을 때 걸리는 최소 비용

 

 

---

 

3. 생각

이론은 학습했지만, TSP 알고리즘에서 처음 접했던 비트마스킹 기법과 시간초과가 났던 경험들을 끄적여본다.

 

1) 비트마스킹

지금까지 방문한 도시들을 저장하는데 비트마스킹이 사용된다.

 

먼저 왜 비트마스킹을 사용할까?

비트마스킹을 사용하지 않으면 일반 리스트를 통해 방문 상태를 표현할텐데,

   이는 dp를 정의하기도 어려울 뿐더러 '도시 이름'이나 '인덱스'에 따라 접근하게 된다.

따라서 각 도시의 방문 상태를 표현하는데 있어서 더 직관적이고, 비트 연산을 활용해 메모리 효율적으로 동작하게끔 한다.

 

비트마스킹을 사용하면 N개의 비트로, 2^N의 상태를 표현할 수 있다.

1번 도시	2번 도시	3번 도시	이진수	십진수
x	x	x	000	0
x	o	x	010	2
o	o	x	011	3
x	o	o	110	6

 

 

 

비트마스킹이 사용된 부분은 다음과 같다.

 

1. dp 배열에서 "지금까지 방문한 노드" 정의

# dp[i][visited] : dp[현재 노드][지금까지 방문한 노드] = 나머지 정점을 이동하고 출발 정점으로 돌아오는데 걸리는 최소 비용
dp = [[0] * (1<<N) for _ in range(N)]

 

 

2. 모든 노드를 방문했는지 체크

if visited == (1<<N)-1:
    if graph[now][start]: # 시작점까지 가는 경로
        return graph[now][start]

    return INF # 없으면 INF 값 반환

 

 

3. 이전에 방문한 노드인지 "&" 연산자, 그리고 방문할 때 "|" 연산자

for i in range(0, N):
    # i가 이전에 방문한 노드인지 판단 ("&")
    if visited & (1<<i):
        continue

    # i 노드를 방문한다. ("|")
    # 그리고, 방문하지 않은 노드들을 방문했을 때 걸리는 최소 비용을 temp에 저장한다.
    temp = dfs(i, visited | (1<<i))

 

 

 

2) 시간초과

처음 문제를 풀 때 dp 초기값을 float('inf') 값으로 설정하고, dfs 탐색을 진행했다.

end 지점에서 출발지까지 가는 경로가 없으면 INF 가 반환된다.

 

이 때, 이미 최소비용이 계산되었으나 "INF"로 초기화 되고

중복 경로 방지 조건이 != INF 에 따라서, 중복 경로를 탐지하지 못하고 계속 dfs 탐색이 일어나 시간초과가 발생한다.

 

따라서 dp 초기값을 0 으로 설정하고, dfs 탐색을 할 때마다 INF로 초기화 해주어야 한다.

그리고 중복 경로 방지 조건을 != 0 일 때로 수정한다.

 

# 설명에 필요한 부분만 간추림

INF = float('inf')
dp = [[INF] * (1 << n) for _ in range(n)]

def dfs(now, visited):
    # 모든 노드를 방문했을 시
    if visited == (1<<N)-1:
        if graph[now][start]: # 시작점까지 가는 경로
            return graph[now][start]

        return INF # 없으면 INF 값 반환


    # 이미 최소비용이 계산되어 있다면
    if dp[now][visited] != INF:
        return dp[now][visited]


    for i in range(0, N):
        # i 노드를 방문한다. ("|")
        # 그리고, 방문하지 않은 노드들을 방문했을 때 걸리는 최소 비용을 temp에 저장한다.
        temp = dfs(i, visited | (1 << i))
    
        # 현재 노드에서 i까지 비용 + temp 와 비교한다.
        dp[now][visited] = min(dp[now][visited], graph[now][i] + temp)

 

 

---

 

4. 코드

N = int(input())
graph = [list(map(int, input().split())) for _ in range(N)]

INF = float('inf')

# dp[i][visited] : dp[현재 노드][지금까지 방문한 노드] = 나머지 정점을 이동하고 출발 정점으로 돌아오는데 걸리는 최소 비용
dp = [[0] * (1<<N) for _ in range(N)]


def dfs(now, visited):
    # 모든 노드를 방문했을 시
    if visited == (1<<N)-1:
        if graph[now][start]: # 시작점까지 가는 경로
            return graph[now][start]

        return INF # 없으면 INF 값 반환


    # 중복 경로일 시 이전 구한 값 return
    if dp[now][visited] != 0:
        return dp[now][visited]


    # 노드 방문
    dp[now][visited] = INF # 방문 표시, 길이 없어도 "if dp[now][visited] != 0"이 무한 재귀가 되지 않도록
    for i in range(0, N):
        if graph[now][i] == 0:
            continue

        # i가 이전에 방문한 노드인지 판단 ("&")
        if visited & (1<<i):
            continue

        # i 노드를 방문한다. ("|")
        # 그리고, 방문하지 않은 노드들을 방문했을 때 걸리는 최소 비용을 temp에 저장한다.
        temp = dfs(i, visited | (1<<i))

        # 현재 노드에서 i까지 비용 + temp 와 비교한다.
        dp[now][visited] = min(dp[now][visited], graph[now][i] + temp)

    return dp[now][visited]


start = 0
bit = 1
print(dfs(start, bit))