#2098 외판원 순회

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

2098번: 외판원 순회

 

외판원 순회는 세계일주 라고 생각하면 된다. 한국에서 출발하는데 가고싶은 나라가 프랑스 독일 영국이라면

한국에서 출발해서 어떻게 나라를 거쳐가서 돌아올때가 가장 경비가 저렴한지의 느낌으로 풀어주면 된다.

이 문제는 비트마스킹을 이용하여 메모이제이션을 활용한 dp문제이다.

 

만약 총 노드가 0,1,2,3 이렇게 4개가 주어지고 0에서 출발했을때 0으로 돌아올 경로의 경우의 수는

0-1-2-3, 0-1-3-2, 0-2-1-3, 0-2-3-1, 0-3-1-2, 0-3-2-1 이다.

 

인덱스 즉 노드의 방문이 다음과 같이 순서대로 거쳐가는것을 알 수 있다.

이제 메모를 활용해야 하는데

 

이 재귀의 상태를 그림으로 그려보면 다음과 같다.

 

먼저 재귀를 통한 탐색을 하게되면 자식노드가 없는 단말 노드까지 쭉 내려간다. 이따 단말노드가 처음으로 가는 경로 즉 arr[단말노드][0(시작노드)] 값이 0이 아니면 arr[단말노드][0(시작노드)]를 리턴해준다. 그러면 맨처음에는 memo[2][1+2+4=7]값은 기존memo[2][7](무한대값)과 이 arr[3][15]값중 min값인arr[3][15]를 선택하고 마찬가지로 memo[3][1+2+8]부분도 같은 방식으로 값이 설정된다. 그 후 memo[1][3]은 이제 자식노드인 memo[2][7] 과 memo[3][11] 중 min값을 선택하게 된다. 이와 같은 방식으로 나머지 노드들도  min값을 선택하게 된다.

 

또한 이 과정에서 메모이제이션을 활용하게 되는데 

이미구한  memo는 min값으로 구해줬는데 만약 memo가 구해진 상태라면 이미 구한 memo를 또 구해줄 필요가 있을까? 그럴필요가 없다. 그래서 memo가 값이 정해진다면 if(memo[노드][비트마스킹값]이 0 이상이라면 해당 값만 리턴을 해서 다시 하위노드로 함수를 호출하는 불필요한 함수호출 반복을 방지해준다.

 

소스코드