본문 바로가기

백준 문제풀이 코드저장소/Gold

Baekjoon 2098. 외판원 순회 / Python

728x90

2098. 외판원순회

난이도 : 골드 1
소요 시간 : 45분
날짜 : 2024.12.22
언어 : 파이선
알고리즘 유형 : 비트마스킹, dp, dfs

설명 보기전에 문제 풀어보러 가기

1. 문제 설명

  1. n 개의 도시가 주어진다.
  2. 도시의 연결은 비용으로 연결된 비대칭그래프이다.
  3. 최소의 비용으로 모든 도시를 순회하고 돌아와야 한다.

2. 해결 방식

비트마스킹과 DP....(그리고 dfs)

  1. DP 배열 설명 : dp는 2차원 배열로써 dp[i][j] 는 도시 i에 도달했고, 방문 상태 j 일 때의 최소비용을 나타낸다.
  2. 비트마스킹 : 방문 상태 j 는 비트마스킹으로 나타낸다. n의 범위가 2 < n < 16 이므로 비트를 사용하기 충분하다.
  3. dfs에서의 가지치기
    3-1. 모든 도시를 방문 한 경우 : 최소값을 갱신할 수 있다.
    3-2. 최소비용이 이미 있는 경우 : 그 값을 재사용한다.
  4. dfs에서의 점화식
    4-1. 식
     dp[now][visit] = min(dp[now][visit], arr[now] + dfs(next, visit | (1 << next))
    4-2. 설명 : 다음 도시로 이동하면서, 다음도시를 방문처리한다. 현재경로 비용 , 다음 경로의 비용의 최소값을 구한다.
  5. 함수 실행 dfs(1, 0)
    • 모든 점을 순회하는 사이클이기 때문에 어느 점에서 시작해도 상관없음.
  6. 시간복잡도 : O(n * 2^n) -> 최대 100만

3. 정답 코드

import sys
sys.stdin = open("C:/Users/ghtjd/Desktop/tmp/python/input.txt", "r")

# input = sys.stdin.readline
inf = 1e10

n = int(input())    # 2 < n < 16

arr = [list(map(int, input().split())) for _ in range(n)]   # 비대칭 그래프
dp = [[-1] * (1 << n) for _ in range(n)] # dp[i][j] : i 에 도달, k = visited인 최소 비용

def dfs(now, visit):
    if visit == (1 << n) - 1:   # 모든 도시 방문
        return arr[now][0] if arr[now][0] > 0 else inf

    # 최소비용 이미 있음 -> 재사용
    if dp[now][visit] != -1: return dp[now][visit] 

    dp[now][visit] = inf
    for next in range(1, n):
        if arr[now][next] == 0:continue # 경로가 없음
        if visit & (1 << next):continue    # 이미 방문함

        # 점화식 - 재귀
        # 1. 현위치(now)에서 다음도시(next)로 이동
        # 2. 방문처리, 최소비용 있는 경우 이미 위에서 체크함
        # 3. dfs + 재귀 -> 비용 갱신
        dp[now][visit] = min(
            dp[now][visit], 
            arr[now][next] + dfs(next, visit | (1 << next))
            )

    return dp[now][visit]

# 사이클이기 때문에 시작을 0으로, 0을 방문 -> visit = 1
res = dfs(0, 1)  

print(res)
반응형