2098번: 외판원 순회
첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j
www.acmicpc.net
비트마스크를 이용한 동적 프로그래밍 + dfs 방법으로 풀 수 있는 문제이다.
아래는 문제 예제의 도시와 경로를 나타낸 것이다.
dp 2차원 배열을 생성한다.
첫번째 인덱스는 현재 위치한 도시, 두번째 인덱스는 여태까지 방문한 도시정보를 비트마스크로 표현한다.
dp[1][0001(2)] : 현재 위치한 곳은 1번 도시이고, 여태까지 방문한 도시는 1번 도시일 때,
전체 도시를 순회하기 위해 남아있는 최소비용
dp[2][0011(2)] : 현재 위치한 곳은 2번 도시이고, 여태까지 방문한 도시는 1,2번 도시일 때,
전체 도시를 순회하기 위해 남아있는 최소비용
dp[4][1111(2)] : 현재 위치한 곳은 4번 도시이고, 여태까지 방문한 도시는 1,2,3,4번 도시일 때,
전체 도시를 순회하기 위해 남아있는 최소비용
전체 도시를 순회하는 경우, 어디서 출발하든지 최소비용은 동일하기 때문에 편의상 1번 도시를 시작도시라고 한다.
1번도시부터 dfs으로 도시들을 하나하나 방문해간다. 이 때, 함수의 매개변수로 현재 노드와 여태까지 방문한 도시의 정보를 비트마스트로 전달한다. 만약, 1,2,3,4번 도시를 모두 방문하고 나면, 그 때의 visit은 위에서 설명한대로 1111(2) = 15가 될 것이다. 이 경우, 더 이상 방문할 도시가 없으므로 재귀를 탈출하는 base case가 된다. 그리고 마지막 도시에서 다시 시작 도시인 1번 도시로 가야 하므로 현재 도시와 1번 도시 사이의 경로의 비용을 반환한다.
예를 들어, 마지막으로 방문한 도시가 4번 도시라면 4번 도시 -> 1번 도시로 가야 하므로 이 때의 비용은 8이 되므로 8을 반환한다.
정답코드 :
'BOJ' 카테고리의 다른 글
| [백준 1562번] 계단 수 (java) (0) | 2021.03.25 |
|---|---|
| [백준 14725번] 개미굴 (java) (0) | 2021.03.25 |
| [백준 9934번] 완전 이진 트리 (java) (1) | 2021.03.23 |
| [백준 1719번] 택배 (java) (0) | 2021.03.23 |
| [백준 5670번] 휴대폰 자판 (java) (0) | 2021.03.21 |