[백준/알고리즘] 10971번 외판원 순회 2 (실버 2)

클릭하면 백준 페이지로 이동합니다.

---

 

BOJ 10971번

 

1번부터 N번까지 번호가 매겨져 있는 도시들이 있다. 도시들 사이에는 길이 있다.(없을 수도 있다.) 어느 한 도시에서 다른 도시로 가는 길이 있다면, 비용이 주어진다. 외판원 순회는 처음 한 도시에서 출발해서, 다른 도시들을 순회한 후 마지막에 처음 도시로 돌아올 때 까지의 최소 비용을 구하는 문제이다. 

 

풀이 알고리즘 : 완전탐색, DFS, 백트래킹?

 

먼저 adj[N][N] 배열에 비용을 모두 입력받는다.

이후 모든 노드에 대해서 각각을 시작 노드로 가정하고 모든 경로를 탐색한다.

 

탐색을 위해서 DFS와 같은 형태로 구현했다.

DFS함수는 이동할 수 있는 모든 경로를 탐색하고, 다시 출발지로 돌아왔을 때 그때까지의 비용의 합과, 현재까지 최소 비용을 비교하여 최신화시키는 함수이다.

 

DFS함수의 인자로 (int stt, int cur, int curcost, int curcity) 4개가 들어오는데,

stt는 맨 처음 시작한 노드, cur는 현재 위치한 노드를 의미한다.

curcost는 현재까지 지불한 비용을 의미하고, curcity는 현재까지 지나온 도시의 개수를 의미한다.

 

만약 모든 노드를 순회하고, stt와 같은 노드로 위치하면 그때의 비용을 리턴하고, 그렇지 않다면 현재 노드에서 길이 있고, 확인하지 않은 모든 노드를 탐색하여 순회가 되는지 확인한다.

 

이때 주의해야하는 점은, 만약 길이 있고, 확인되지 않았다면, check배열을 true로 바꾸고, DFS함수를 재귀로 호출해서 탐색한 후, 다시 check배열을 false로 바꿔주어야 한다. 그렇지 않으면, 모든 경우의 수를 탐색할 수 없기 때문에 답을 찾지 못할 수 있다.

 

소스코드 보기

 

#include <bits/stdc++.h>
// 2의 제곱수 판정
#define POW2(X) (X) == ((X)&(-(X)))

// 기본설정
typedef long long ll;
using namespace std;
int dirx[4] = {1, 0, -1, 0};
int diry[4] = {0, 1, 0, -1};

// 전역변수
int city, mincost = 1000000000;
int adj[10 + 1][10 + 1] = {0};
bool check[10 + 1] = {false};

// DFS함수
int dfs(int stt, int cur, int curcost, int curcity) {
	if(curcity == city && stt == cur) {
		// 순회 완료 (탈출조건)
		return curcost;
	}

	int m = 1000000000;

	for(int dst = 0; dst < city; dst++) {
		if(cur == dst) {
			// 자기자신으로는 이동 불가
			continue;
		} else if(!check[dst] && adj[cur][dst] != 0) {
			// 확인하지 않았고, 길이 있는 경우
			check[dst] = true;
			m = min(m, dfs(stt, dst, curcost + adj[cur][dst], curcity + 1));
			check[dst] = false;
		} else if(curcity == city - 1 && dst == stt && adj[cur][dst] != 0) {
			// 다른 모든 도시를 순회했고, 다시 출발지로 가는 길이 있는 경우
			m = min(m, dfs(stt, dst, curcost + adj[cur][dst], curcity + 1));
		} else if(curcity == city - 1 && dst == stt && adj[cur][dst] == 0) {
			// 다른 모든 도시를 순회했고, 다시 출발지로 가는 길이 없는 경우
			return 1000000000;
		}
	}

	return m;
}

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

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

	// 모든 노드에 대해서, 각각을 시작 노드로 보고 완전탐색
	for(int stt = 0; stt < city; stt++) {
		memset(check, 0, sizeof(check));
		check[stt] = true;
		mincost = min(mincost, dfs(stt, stt, 0, 0));
	}

	cout << mincost;

	return 0;
}