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

---

처음에 그래프문제인줄 알고 그래프문제로 접근할려고 했더니 시간초과가 계속 발생하였다. N이 16이라 16!이기 때문에 일반 그래프의 dfs로는 해결할 수 없다. 따라서 생각할 수 있는 방식이 비트마스킹이다.

 

왜냐하면 방문처리를 다음과 같이 해주어야한다. N이 만약에 5라면 visited[row][0][1][2][3][4] = False 즉, 어느 행에 도착했을때 내가 지나온 노드들을 방문처리를 해주어야하는데 다음과 같이 모든 노드들을 방문처리를 해줄경우 5 ^ 6 개의 처리를 해주어야하기 때문에 N이 16이라면 16 ^ 17 이라 사실상 불가능하다. 이때 생각할 수 있는것이 비트마스킹 방문처리이다.

 

처음에는 단순히 각 지점(0~N - 1)에서 출발해서 각각의 거리 최솟값을 구한후 젤 작은 값을 출력하는 방식으로 했는데 생각해보니 그냥 노드0 한 점에서만 출발한 후 검사해도 모든 경로를 검사할 수 있었다. 그래서 0에서만 출발해서 검사하는 방식으로 바꾸었다.

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


def dfs(row, visit, start, cnt):
    if cnt == N:
        return 0

    if visited[row][visit] != -1:
        return visited[row][visit]

    ret = 10000000
    for i in range(N):
        if visit & (1 << i) != 0 or city[row][i] == 0:  # 해당 노드를 이미 방문했거나 연결되어있지 않다면
            continue
        # 만약 마지막 방문 도시인데 처음도시를 선택하지 않았거나 현재 마지막 방문 도시가 아닌데 처음도시를 선택한 경우는 continue
        if (cnt == N - 1 and i != start) or (cnt != N - 1 and i == start):
            continue

        ret = min(ret, dfs(i, visit | (1 << i), start, cnt + 1) + city[row][i])

    visited[row][visit] = ret

    return visited[row][visit]


print(dfs(0, 0, 0, 0))