[Python/Baekjoon] 2098. 외판원 순회

💬 문제

문제 난이도: 백준 골드 1

문제 링크: https://www.acmicpc.net/problem/2098

❗️접근 방법

• 비트마스킹, DFS, DP 3가지 개념을 사용해서 풀 수 있다.
• 비트마스킹: 방문 체크를 하기 위함
  (0001: 0번째 노드만 방문함. 0101: 0번째, 2번째 노드만 방문함) <- 이때, 0001, 0101...은 2진법!
• DFS: 시작점에서부터 가능한 모든 노드를 방문하기 위함
• DP: 현재 노드에서 모든 노드를 방문했을 때의 최소 비용을 기억하기 위함
  - dp[현재노드][방문이력] = 현재노드에서부터 방문하지 않은 노드를 방문하고 다시 시작점으로 돌아갔을 때의 최소 비용 (아래 설명 참고)
• TSP(Traveling Salesman Problem): 시작점을 포함해서 모든 노드를 방문하고 새롭게 방문하는 마지막 노드에서 다시 시작점으로 돌아왔을 때에 사용한 비용의 총합을 최소로 만들고 싶다!
  -> 사이클이 만들어짐 (만들어져야 함)
  -> 임의의 노드를 시작점으로 내가 선택해도 문제 없음.
  (시작점으로 돌아올 수 있을 때의 경로들 중에서 최소 비용을 구하고 싶은거니까)

💢 답은 나오지만 시간초과나는 코드

# 외판원 순회
import sys
input = sys.stdin.readline
print = sys.stdout.write

N = int(input())
graph = []
for _ in range(N):
    graph.append(tuple(map(int, input().split(' '))))

dp = [[sys.maxsize]*(1<<N) for _ in range(N)]

def dfs(x, visit):
    if visit == (1<<N)-1:
        if graph[x][0] != 0:
            return graph[x][0]
        else:
            return sys.maxsize

    if dp[x][visit] != sys.maxsize:
        return dp[x][visit ]

    for i in range(1, N):
        if graph[x][i] == 0:
            continue
        if visit & (1<<i):
            continue
        dp[x][visit] = min(dp[x][visit], dfs(i, visit|(1<<i))+graph[x][i])
    return dp[x][visit]

print(f'{dfs(0, 1)}')

✅ 정답 코드

# 외판원 순회
import sys
input = sys.stdin.readline
print = sys.stdout.write
sys.setrecursionlimit(10**8)

N = int(input())
graph = []
for _ in range(N):
    graph.append(tuple(map(int, input().split(' '))))

# 1<<N == 1*2^N
dp = [[0]*(1<<N) for _ in range(N)]

# x: 현재 위치
# visit: 현재 위치를 포함해서 방문한 이력
def dfs(x, visit):
	# 이미 인자로 받은 visit 정보와 함께 x에 온 이력이 있는지 
    	# 있다면 0(초기값)이 아닐 것 -> 최소 비용이 이미 dp에 담겨 있을 것
        # 없다면 0(초기값)일 것 -> if 조건에 맞지 않음
    if dp[x][visit]:
        return dp[x][visit]
	
    # 모든 노드를 방문했는지
  		# 했다면 마지막 노드(현재 노드==x)에서 0(시작점)으로 돌아갈 방법이 있는지
    if visit == (1<<N)-1:
        if graph[x][0]:
            return graph[x][0]
        return sys.maxsize

	# 위의 if문들의 조건 모두 맞지 않아 여기까지 왔다는 것은
    # 인자로 주어진 visit 정보로 x라는 노드에 처음 방문했다는 의미
    	# 주어진 visit을 통해 방문한 적 없는 노드가 무엇인지 알고
    	# 그곳들을 방문했을 때의 최소비용을 알아내야 함
    min_cost = sys.maxsize
    for i in range(1, N):
    
    	# 현재 위치(x)에서 i로 가는 방법이 없거나
        # 이미 i 노드를 방문한 이력이 visit에 담겨 있다면 
        if not graph[x][i] or visit & (1<<i):
            continue
            
        # dfs로 방문하지 않은 노드들을 방문해줘야 함
        # visit | (1<<i)로 i번째 노드까지 방문했다는 것을 표시하고
        # graph[x][i]를 더해줌으로써 x->i로 갈 때 필요한 비용을 더함
        tmp = dfs(i, visit|(1<<i))+ graph[x][i]
        
        # 최소 비용을 알고 싶기 때문에 
        # 현재 위치 x에서 방문하지 않은 노드를 방문하는 여러가지 방법들 중 최소 비용으로 min_cost를 갱신함
        if tmp < min_cost:
            min_cost = tmp
    dp[x][visit] = min_cost
    return min_cost

print(f'{dfs(0, 1)}')

(참고한 코드: https://hongcoding.tistory.com/m/83)
(참고한 코드: https://velog.io/@piopiop/%EB%B0%B1%EC%A4%80-2098-%EC%99%B8%ED%8C%90%EC%9B%90%EC%88%9C%ED%9A%8C-Python)

✍️ dp[x][visit]가 어떻게 최소 비용을 담고 있는 걸까?

• x의 의미는 "현재 위치(노드)"이다.

• dp[x][visit]에 담길 정보는 (시작점이 아니라) 현재 위치 x에서부터 방문하지 않은 노드들을 모두 방문하고 시작점으로 돌아갔을 때의 최소비용이다.

• 가령 노드가 4개있고(0, 1, 2, 3), 0번 노드가 시작점이라고 하자.
  dp[1][0011]의 의미는
  1) 현재 위치는 1이다.
  2) 2, 3은 아직 방문하지 않은 상태이다.
  3) 이때, 0(시작점) -> 1 -> 2 -> 3 -> 0 경로로 갈 수도 있고 0(시작점) -> 1 -> 3 -> 2-> 0 경로로 갈 수도 있다.
  4) 두 경로의 비용이 다를 수 있는데, (처음 0->1 의 비용을 아직 더하지 않은 상태에서의) "최소비용"이다.
  5) 즉, 1->2->3->0의 비용과 1->3->2->0 중에서 최소 값을 dp[1][0011]을 가지고 있다.

• 외판원 순회 문제의 경우 끝지점이 정해져 있고, dfs로 끝까지 방문하기 때문에 dp[x][visit]가 현재 위치 x에서부터 아직 방문하지 않은 노드를 방문하고 다시 0으로 돌아갈 때의 최소 비용을 담고 있을 수 있는 것이다.

  (논리구조가 유사한 문제: https://www.acmicpc.net/problem/2253)

  

Dynamically difficult
Programming