[백준] 10971 외판원 순회 2

 

✔️ 문제 링크

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

10971번: 외판원 순회 2

---

✔️ 문제 이해

1. N개의 도시가 존재하고, 각 도시는 도로로 연결되어 있다. 각 도시간에 이동할때 비용을 지불해야한다.

2. W[i][j]는 도시 i에서 도시 j로 가기 위한 비용을 나타낸다. 비용은 대칭적이지 않다. 즉, W[i][j] 는 W[j][i]와 다를 수 있다.

3. 가장 적은 비용을 들이는 외판원 순회 경로를 구하면 된다. 

---

✔️ 설계

1. N개의 도시를 순서대로 나열하는 방법은 N!이다. N의 제한이 10이므로 10!의 시간이 걸린다. 완전탐색으로 충분히 풀 수 있다. 

---

✔️ 문제 회고

1. 재귀 호출을 통한 완전탐색에 좀 더 익숙해져야겠다. 

---

👨🏻‍💻 소스 코드

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int n;
int dist[10][10];
int start;

int shortestPath(vector<int>& path, vector<bool>& visited, int currentLength) {
	
	//모든 도시를 방문했고, 현재 위치에서 출발지인 0번 도시로 돌아갈 수 있으면 재귀 종료
	if (path.size() == n && dist[path.back()][start] != 0)
		return currentLength + dist[path.back()][start];

	int ret = 2e9;

	for (int next = 0; next < n; next++) {
		if (visited[next]) continue; //이미 방문한 도시인 경우
		int here = path.back();
		if (dist[here][next] == 0) continue; //이동이 불가능한 경우 

		path.push_back(next);
		visited[next] = true;
		int candi = shortestPath(path, visited, currentLength + dist[here][next]);
		ret = min(ret, candi);
		visited[next] = false;
		path.pop_back();
	}
	return ret;

}

int main() {

	cin >> n;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> dist[i][j];
		}
	}

	vector<int> path;
	vector<bool> visited(n,false);

	//0번 도시에서 출발
	start = 0;
	path.push_back(0);
	visited[0] = true;
	cout << shortestPath(path, visited, 0);

	return 0;
}