[파이썬] 백준 2098 : 외판원 순회 (골드1)

[파이썬] 백준 2098 : 외판원 순회 (골드1)

2098번: 외판원 순회

---

문제

 

---

풀이

 

0. 방향성 생각

• 상태가 많이 존재 -> 비트마스킹
• 경로 탐색 -> BFS

1. 입력

import sys
sys.setrecursionlimit(10**6)

n = int(input())
w = {i:dict(zip(range(n),list(map(int,input().split())))) for i in range(n)}
dp = [[-1]*(n) for _ in range(1<<n)]
INF = 1e8

• dp[상태][마지막 방문 노드]
• 상태 = 몇 번 노드를 방문했는지

2. 함수 정의

def dfs(x,state):
    if state == (1<<n)-1:
        if w[x][0] != 0: return w[x][0]
        else: return INF

    if dp[state][x] != -1:
        return dp[state][x]

    dp[state][x] = INF
    for nx in range(n):
        if not (state&(1<<nx)) and w[x][nx] != 0:
            dp[state][x] = min(dp[state][x], dfs(nx,state|(1<<nx))+w[x][nx])

    return dp[state][x]

• 모두 방문하는 경우에 탈출조건을 넣는다.
• 모두 방문한 후 사이클이 생겨야한다. 마지막 방문지점 x에서 첫 도시 0으로 올 수 있으면 그 값을 리턴, 아닌 경우 INF 리턴
• 하위 노드에서 올라올 때 dp값이 있으면 메모제이션을 사용
• for문에서 다음 노드가 연결되어있고 방문하지 않았으면 방문.
• 현재 저장된 dp[state][x] 값과 dfs+w[x][nx] (다른 루트에서 온 값)를 비교하여 최소값을 선택한다.

 

---

전체코드

import sys
sys.setrecursionlimit(10**6)

n = int(input())
w = {i:dict(zip(range(n),list(map(int,input().split())))) for i in range(n)}
dp = [[-1]*(n) for _ in range(1<<n)]
INF = 1e8

def dfs(x,state):
    if state == (1<<n)-1:
        if w[x][0] != 0: return w[x][0]
        else: return INF

    if dp[state][x] != -1:
        return dp[state][x]

    dp[state][x] = INF
    for nx in range(n):
        if not (state&(1<<nx)) and w[x][nx] != 0:
            dp[state][x] = min(dp[state][x], dfs(nx,state|(1<<nx))+w[x][nx])

    return dp[state][x]

print(dfs(0,1))

 

코멘트

질문 게시판에 있는 시간 초과 해결 글을 보고나서 고쳤다.

중요한건 메모제이션인데 처음에 푼 풀이는 DP배열에서 inf와 방문처리를 구별 할 수 없어서 메모제이션이 안되는 문제가 발생했다.

이를 해결하려면 DP 초기값을 다르게 설정하거나 visit을 따로 만드는건데 n이 커지질수록 visit 크기가 지수적으로 증가해서 메모리 손해가 크다.

그래서 DP 초기값을 -1로 초기화하고 사이클이 안생기는 경우 inf를 리턴했다. 

 

DFS + DP 계속 푸니까 감은 잡았는데 이런 환형, 사이클 문제 들어가면 난이도가 너무 어려워짐....