[BOJ-2098] 외판원 순회 (C++)

백준 2098 외판원 순회

 

2098번: 외판원 순회

 

문제 설명

 

 - 1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다.

 

 - 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획한다.

 

 - 한 번 갔던 도시로는 다시 갈 수 없다.(맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외)

 

 - 이런 여행 경로 중 가장 적은 비용이 걸리는 여행 계획을 세우자.

 

---

 

입력 값

 

 - 첫째 줄에 도시의 수 N( 2<= N <= 16 )이 주어진다.

 

 - 다음 N개의 줄에는 비용 행렬이 주어진다.

 

 - 각 행렬의 성분은 100만 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다.

 

 - 자기 자신으로 가는 경우는 0이 된다.

 

 - 항상 순회할 수 있는 경우만 입력으로 주어진다.

---

 

 

예제

---

 

문제 분석

 

 - 이 문제는 특정 위치에서 시작하여, 모든 노드를 거친 뒤 현재 위치로 돌아오는 최소 비용을 찾는 문제이다.

 

 - 이 문제를 해결하는 가장 중요한 부분은 똑같은 계산을 다시 반복하지 않는 것이다.

 

 - 다시 반복하지 않는 다는 것은, 1, 2, 3번 도시를 돌아 4번 도시에 도착했다고 가정하자.

   그렇다면 4번에서 시작하여 5, 6 ,7 번 도시를 돌고 다시 1번으로 돌아야 한다.

 

 - 내가 1 -> 2 -> 3 의 경로를 거쳐서 4번에 도착한 후 나머지 경로를 계산한다.

   다른 경우의 수로 1 -> 3 -> 2 의 경로를 거쳐서 4번에 도착했을 때 이미 1 -> 2 -> 3의 경로를 거쳐

   도착했을 때 나머지 경로를 계산했기 때문에 다시 계산할 필요가 없다는 것이다.

 

 - 즉, 내가 어떠한 도시들을 거쳐왔고, 어떠한 도시를 거쳐가야 하는지 알고 있다면 반복 계산을 방지할 수 있다.

 

 - 문제 해결 방법은

   0. visited[N][i] 를 선언한다.

      visited[N][i] 는 N은 이미 거쳐 온 도시를 이진수로 표현한 것이고, 이 도시들을 거쳐 i번에 도착했다는 것이다.

      visited[N][i] 에 들어갈 값은 i에서 시작하여 N에 없는 도시들을 거쳤을 때 최소값을 저장하는 것이다.

   1. 임의의 시작 원소를 결정하여 해당 원소를 시작으로 dfs를 시작한다.

   2. 도시를 거치게 되는 경우, visited에 해당 값이 있는지 확인한다.

   3. 이미 값이 존재한다면, 해당 값을 사용한다.

   4. 값이 존재하지 않는다면, 해당 도시를 시작으로 하는 dfs를 시작한다.

   5. 위 과정을 반복하여 최소값을 찾는다.

 

 

---

 

 

소스 코드

 

#include <bits/stdc++.h>

using namespace std;

int N;

int visited[(1 << 16)][17];

int boards[17][17];

int last;

int maxNum = 16000001;

int dfs(int now, int cnt) {

	// 모든 경로 탐색 완료
	if (cnt == last) {
		return 0;
	}

	// 이미 값이 있는지 확인
	if (visited[cnt][now] != maxNum) {
		return visited[cnt][now];
	}

	for (int i = 0; i < N; i++) {

		int nextCost = boards[now][i];

		// 갈 수 없는 경로 or 이미 지나간 도시인 경우 
		if (nextCost == 0 || (cnt & (1<<i))) {
			continue;
		}

		// i번째 도시 지나갔다고 표시
		int nextCnt = cnt | (1 << i);

		// 시작점으로 도착했는데 모든 도시를 지나지 않은 경우
		if (i == 0 && nextCnt != last) {
			continue;
		}

		// 해당 경로에서 시작하는 최소값 찾기
		visited[cnt][now] = min(visited[cnt][now], dfs(i, nextCnt) + nextCost);

	}

	return visited[cnt][now];

}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;

	last = (1 << N)-1 ;

	fill(&visited[0][0], &visited[0][0] + (last+1) * 17, maxNum);

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			int c;
			cin >> c;
			boards[i][j] = c;
		}
	}

	cout << dfs(0, 0) << endl;

	return 0;
}