백준 2098 외판원 순회

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

2098번: 외판원 순회

 

비트마스킹 + dp + dfs

 

1. 출발 도시는 어느 지점이든 상관없다. 어차피 구한 경로는 사이클을 이루기 때문.

2. 방문한 도시는 비트마스킹으로 표시한다. 

3. dp에는 현재 도시에서 남은 도시들을 거쳐 다시 출발점으로 돌아오는 비용이 저장된다.

dp[row][visit] = 현재 row 도시이며, 방문현황은 visit와 같고, 아직 방문하지 않은 도시들을 모두 거쳐 다시 시작점으로 돌아가는데 드는 최소 비용

 

dp[next][nextvisit] = next도시에서 남은 도시를 거쳐 시작점으로 돌아가는 최소 비용

dp[row][visit] = dp[next][nextvisit] + graph[row][next]가 될 것이다.

 

이를 점화식으로 나타내면

dp[row][visit] = min(dp[row][visit], dp[next][visit | (1<<next)] + graph[row][next])

 

4. dfs를 통해 dp값을 갱신시켜준다.

 

N = int(input())
city = [list(map(int, input().split())) for _ in range(N)]
dp = [[-1 for _ in range(1 << N)] for _ in range(N)]


def dfs(now, visit, cnt):
    if cnt == N:
        return 0
    if dp[now][visit] != -1:
        return dp[now][visit]

    tmp = float("inf")
    for i in range(N):
        if visit & (1 << i) != 0:  # 방문했으면
            continue
        if city[now][i] == 0:
            continue
        if cnt == N - 1 and i != 0:  # 사이클이 이루어지지 않는 경우
            continue
        if cnt != N - 1 and i == 0:  # 다른 노드 방문 전에 출발지 방문하는 경우
            continue
        # tmp = min(tmp, dp[i][visit | (1 << i)] + city[now][i])
        tmp = min(
            tmp, dfs(i, visit | (1 << i), cnt + 1) + city[now][i]
        )  # dp값을 dfs에서 리턴 받기
    dp[now][visit] = tmp
    return dp[now][visit]


# 시작 지점 0으로 잡음
print(dfs(0, 0, 0))

 

 

 

https://hongcoding.tistory.com/83

[백준] 2098 외판원 순회 (Python 파이썬)

https://ji-gwang.tistory.com/448

백준 2098번 파이썬 문제풀이(외판원 순회 ) - (dfs + 비트마스킹 + dp)