[ 백준 2098번 ] 외판원 순회 파이썬

[백준 2098번 바로가기]

2098번: 외판원 순회

---

유튜브 주니온 TV 아무거나 연구소 강의를 참고했습니다.
[유튜브 주니온TV 강의 바로가기]

 

손글씨로 대체합니다

 

논리 및 점화식

• 집합 연산은 비트마스킹을 이용했습니다(아래에 간단한 설명 첨부했습니다)

표기의 의미

점화식

 원하는 값을 구하는 과정(top-down); 실제 구현은 bottom-up으로 원소 개수가 0인 집합부터 차례로 채워 나갔습니다.

비트마스킹

집합 연산에 이용된 비트마스킹

코드

import sys


def 외판원순회():

    # bit-masking functions
    # 원소 포함 여부 확인
    def isIn(A: int, i: int):
        return (A & (1 << (i-1))) != 0

    # 차집합
    def diff(A: int, i: int):
        return (A & ~(1 << (i-1)))

    # 원소 개수 반환
    def count(A, n):
        cnt = 0
        for i in range(n):
            if (A & (1 << i)):
                cnt += 1
        return cnt

    def min_path(A: int, i: int):   
        # A: integer interpreted as binary number --> representation of a subset
        # i: starting point (destination is 1)

        next = 0
        # minimum = sys.maxsize
        minimum = sys.maxsize
        for j in range(1, N):
            # 비트마스킹: 원소 포함 여부
            if isIn(A, j):
                # 비트마스킹: 차집합
                temp = W[i][j] + D[j][diff(A, j)]
                if temp < minimum:
                    minimum = temp
                    next = j
        return minimum, next

    # inputs
    N = int(sys.stdin.readline())
    W = [None] * N
    for i in range(N):
        W[i] = [j if j != 0 else sys.maxsize for j in list(map(int, sys.stdin.readline().split()))]
        W[i][i] = 0

    size = 2 ** (N-1)
    D = [[0] * size for _ in range(N)]
    P = [[0] * size for _ in range(N)]

    # base case(A: 공집합)
    for i in range(1, N):
        D[i][0] = W[i][0]

    # fill D matrix order of 1 .. N-2(number of elements of A)
    # 원소의 개수가 k인 것만 관심을 가질 예정이다
    for k in range(1, N-1):
        # k가 정해지면
        # 모든 A들 중에
        for A in range(1, size):
            # 비트마스킹: 원소 개수 파악
            # n(A) == k: 원소의 개수가 k인 것만 거른다
            if count(A, N-1) == k:
                # 'start' is not in A
                for start in range(1, N):
                    # 비트마스킹: 원소 포함 여부
                    if not isIn(A, start):
                        D[start][A], P[start][A] = min_path(A, start)

    # last case; start is 1 --> D[1][size-1]
    D[0][size-1], P[0][size-1] = min_path(size-1, 0)

    print(D[0][size-1])
    return

외판원순회()