백준 - 외판원 순회(2098)

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

2098번: 외판원 순회

 

 

나에겐 어려운 문제였다.

계속 시간초과 나서 풀이를 확인했다.

시간초과를 해결하는게 핵심이었다.

 

data = []
n = int(input())
def dfs(cur_node, visited):
    if visited == pow(2, n)-1:
        if data[cur_node][0] != 0:
            return data[cur_node][0]
        else:
            return float('INF')

    if (visited, cur_node) in dp: # 1 2 3 4 5 1 경로와 1 3 2 4 5 1이 있을때 451이 겹침 이 부분은 값만 리턴
        print(visited, cur_node)
        return dp[(visited, cur_node)]
    min_cost = float('INF')
    for i in range(n):
        if (visited >> i) % 2 == 1 or data[cur_node][i] == 0:
            continue
        cost = dfs(i, visited | pow(2, i)) + data[cur_node][i]
        min_cost = min(cost, min_cost)
    dp[(visited, cur_node)] = min_cost
    return min_cost

for i in range(n):
    data.append(list(map(int, input().split())))

dp = {}
print(dfs(0, 1))
print(dp)

이동한 경로에 대해서는 list로 활용을 했으나 방문 검사를 하는데

많은 시간이 걸렸다.

그래서 비트마스킹을 이용했다.

 

dp리스트를 제거해도

정답은 똑같이 나온다

하지만 시간초과가 난다.

 

예를 들어

경로가

1 2 3 4 5 1

1 3 2 4 5 1

을 보면

4 5 1의 경로가 겹친다.

dp리스트에 4 5 1에 대한 코스트를 저장하면

굳이 탐색을 더 할필요가 없고 나중에 꺼내 쓰면 된다.

좋은 아이디어이다.

 

dp와 재귀 연습을 더 해야겠다.