[백준 | BOJ] 2098번: 외판원 순회 (Python)

문제

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

난이도

알고리즘 분류

DFS/BFS
DP
비트마스킹

요약

BFS를 사용하면 다익스트라(Dijkstra) 알고리즘과 매우 흡사한 방식으로 풀 수 있다.
BFS보다 DFS가 메모리, 속도 측면에서 결과가 더 좋았다. (BFS 방식 코드를 잘못 짰을수도...)
위: DFS, 아래: BFS

문제 접근 방식

우선 어떤 알고리즘을 사용해야 하는지 확인하기 위해 문제의 조건들을 살펴보자.

외판원의 순회 여행 경로를 구해야 한다.
- 출발지에서 시작해서 다시 출발지로 돌아와야 한다는 뜻이죠. 즉, 순환경로(Cycle)라는 의미입니다.
- 모든 노드를 방문해야 하므로 DFS/BFS를 사용해야 하는 것을 알 수 있습니다.
가장 적은 비용으로 순회해야 한다.
- "가장 적은 비용" 어디서 많이 보던 단어죠? 최단 경로 탐색 알고리즘을 공부하고 오셨다면 익숙하실겁니다. 거기서 배운 알고리즘들이 DP를 활용한 알고리즘입니다!
- 따라서 DP를 사용해야 한다는 것을 알 수 있습니다.
방문 도시를 어떻게 체크할 것인가?
- Set을 사용하거나 비트마스킹을 사용하는 방법이 있습니다. 하지만 Set을 사용하면 (시작도시, 도착도시) 쌍의 cost를 모두 기록해야 하므로 연산량이 비트마스킹보다 다소 많아질 수 있습니다.
- 효율적인 알고리즘을 원한다면 비트마스킹을 사용하도록 합시다. (비트마스킹을 익히려고 푸는 문제이기도 하고...)

풀이 과정

출발지 선택
- 먼저 출발지를 골라야 합니다. 하지만 사실 한붓그리기를 하듯이 출발지를 잘 고를 필요는 없습니다.
- 문제에서 그래프는 "순회 여행 경로" 즉, 사이클을 이루기 때문에, 출발 지점을 어느 지점으로 정하든지 순회 비용이 동일합니다. 왜 그런지는 아래 그림을 보시죠.
  
  위 그래프에서 시작 지점을 0번 도시부터 차례대로 정해보겠습니다.
  
  1번 시작시 사이클은 (0 → 1 → 2 → 3 → 0) 이 때 비용은 2+3+4+5=14입니다.
  2번 시작시 사이클은 (1 → 2 → 3 → 0 → 1) 이 때 비용은 3+4+5+2=14입니다.
  3번 시작시 사이클은 (2 → 3 → 0 → 1 → 2) 이 때 비용은 4+5+2+3=14입니다.
  4번 시작시 사이클은 (3 → 0 → 1 → 2 → 3) 이 때 비용은 5+2+3+4=14입니다.
  
  사실 이렇게 다 해 볼 필요 없이 사이클을 돌려면 모든 비용을 한 번 씩 거쳐야 하므로 출발 지점과 관계없이 전체 비용은 동일합니다.
방문 경로 체크
- 위에서 방문 경로를 비트마스킹으로 체크할 수 있다고 했습니다. 체크하는 방법은 다음과 같습니다.
  1. 도시(노드)의 개수가 N일 때, N비트짜리 정수를 사용합니다.
  2. 예를 들어, 위 그림과 같이 4개의 도시가 있는 경우를 생각해봅시다. 이 때, 모든 도시를 방문 했는지 안했는지 체크하기 위한 경우의 수는 총 16가지(2^4) 입니다.
  3. 이를 비트로 표현하면 0000 ~ 1111로 표현할 수 있고, 각 자리는 i번 도시의 방문 여부를 나타냅니다.
  4. (2^0) 자리는 0번 도시, (2^1) 자리는 1번 도시, (2^2) 자리는 2번 도시, (2^3) 자리는 3번 도시이고, 방문한 경우 1, 방문하지 않은 경우는 0으로 표시합니다.
순회 비용 저장
- 순회 비용은 DP를 사용하여 저장하면 됩니다.
- dp[current][visited] = 현재 current 도시에서 방문 경로가 visited일 때, 남은 도시를 방문하고 시작점으로 돌아오는 최소 비용
- 예를 들어, 현재 도시가 2번 도시이고, 방문 경로가 0011(0, 1번 도시 방문)이라면 이 때, 남은 도시를 방문하고 시작점으로 돌아오는 최소비용 min_cost = dp[2][3]이 됩니다.

코드 설명

핵심이 되는 tps 함수만 살펴 보겠습니다.

def tps(current, visited):
    global N, W, dp

    check = dp[current][visited]

    # 이미 방문한 도시인 경우
    if check != -1:
        return check

tps 함수는 current, visited를 매개변수로 받습니다.

tps(current, visited) = 현재 curruent 도시에서 방문 경로가 visited일 때, 남은 도시를 방문하고 시작점으로 돌아오는 최단거리

dp 는 -1로 초기화 되어 있기 때문에 -1이 아니면 이미 방문한 적이 있다는 뜻입니다.

현재 도시에 와본적이 있고 방문 경로까지 똑같다? 그럼 이미 동일한 경로로 와봤던 곳이기 때문에 남은 도시들을 방문해 볼 필요가 없겠죠? 그러니 해당하는 값(비용)을 리턴해줍니다.

    # 모든 도시를 방문한 경우
    if visited == (1 << N) - 1:
        # 현재 위치에서 시작점으로 되돌아 갈 수 있음
        if W[current][0] != 0:
            return W[current][0]
        # 현재 위치에서 시작점으로 되돌아 갈 수 없음
        else:
            return sys.maxsize

(1 << N) -1이 무엇을 의미할까요? N=4일 때를 가정해 보면, 이진수로 1111이 됩니다. 맞습니다, 모든 도시를 방문한 경우 입니다.

W[currenct][0]은 현재 도시 current에서 시작지점인 0번 도시로 이동하는 비용을 의미합니다.

문제에서 이 값이 0인 경우 연결되어 있지 않은 도시라고 주어졌네요.

이 값이 0이 아니라면 시작점으로 돌아가면 되고, 0이라면 다음에는 같은 도시에 같은 경로로 방문할 일이 없도록 방문 비용을 매우 큰 값으로 리턴해줍니다.

    # 도시 방문 시작
    min_cost = sys.maxsize
    for i in range(N):
        if visited & (1 << i) or W[current][i] == 0:  # 방문할 수 없는 도시면 패스
            continue

        min_cost = min(min_cost, tps(i, visited | (1 << i)) + W[current][i])

    dp[current][visited] = min_cost

    return dp[current][visited]

이제 기저 조건이 끝나고 본격적으로 도시를 방문하기 시작합니다.

visited & (1 << i)는 이미 방문했던 도시를 다시 방문하지 않도록 중복 체크를 합니다.

(1 << i)는 2^i번 비트만 1이고 나머지는 0인 값입니다. 이 값과 visited를 &(AND)연산 했을 때 i번 도시 방문 여부를 알 수 있습니다.

이미 방문 했다면 visited의 2^i번 비트는 1일 것이고 그렇지 않으면 0일 것입니다.

그렇다면 &(AND) 결과값이 1인 경우 방문했던 도시임을 알 수 있고, 결과값이 0인 경우 방문하지 않은 도시임을 알 수 있습니다.

W[current][i] == 0인 경우 현재 current 도시에서 i번 도시로 이동할 수 있는 경로가 없는 것을 의미합니다.

방문이 불가능한 도시들을 걸러낸 후 재귀 호출로 도시를 방문합니다.

visited | (1 << i)는 방문경로 추가를 의미합니다. (1 << i)와 |(OR) 연산을 하면 i번 비트(도시)를 무조건 1로 만들게 됩니다. 즉, 다음에 내가 방문할 곳은 i번 도시라는 의미가 됩니다.

i번 도시에 방문할 경우의 비용을 구해야 하기 때문에 W[current][i]를 더해줍니다.

반복문으로 모든 도시를 돌고 나면 min_cost값이 계산이 됩니다.

현재 current 도시에서 출발하여 모든 경로를 탐색했으므로 dp[current][visited]에 최소 비용인 min_cost를 저장해줍니다.

전체 코드

# DFS
import sys

sys.setrecursionlimit(10 ** 7)


def tps(current, visited):
    global N, W, dp

    check = dp[current][visited]

    # 이미 방문한 도시인 경우
    if check != -1:
        return check

    # 모든 도시를 방문한 경우
    if visited == (1 << N) - 1:
        # 현재 위치에서 시작점으로 되돌아 갈 수 있음
        if W[current][0] != 0:
            return W[current][0]
        # 현재 위치에서 시작점으로 되돌아 갈 수 없음
        else:
            return sys.maxsize

    # 도시 방문 시작
    min_cost = sys.maxsize
    for i in range(N):
        if visited & (1 << i) or W[current][i] == 0:  # 방문할 수 없는 도시면 패스
            continue

        min_cost = min(min_cost, tps(i, visited | (1 << i)) + W[current][i])

    dp[current][visited] = min_cost

    return dp[current][visited]


def main() -> None:
    global N, W, dp

    input = sys.stdin.readline

    N = int(input().rstrip('\n'))
    W = [list(map(int, input().rstrip('\n').split(' '))) for _ in range(N)]
    dp = [[-1] * (1 << N) for _ in range(N)]

    print(tps(0, 1))


if __name__ == "__main__":
    main()

흔한 개발자의 삶