[백준/C++] 외판원 순회 (No. 2098)

 

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

외판원 순회 문제의 풀이에 대한 개념은 예전에 공부해서 알고 있었다.

 

하지만 이를 실제로 문제에 적용해 보는 것은 처음이라 머릿속에서 바로 구현이 떠오르지 않았다.

 

맨 처음 푼 방법은 [시작마을][직전에 방문한 마을][방문한 마을을 표시하는 비트] 정보를 저장할 3차원 vector를 만들어 BFS로 탐색을 하는 것이었다.

 

실제로 이렇게 풀었더니 매우 직관적이어서 쉽게 구현이 됐다.

 

이후에 다른 사람들의 코드를 보고 시작마을을 정하고 탐색을 시작해도 된다는 사실을 깨달았다.

 

생각해보니 A 마을에서 시작해 A 마을로 돌아오기 때문에 원과 같은 형태로 경로가 형성되기 때문에 시작마을을 특정해도 됐었다...

 

그래서 DFS로 구현할 때는 [직전에 방문한 마을][방문한 마을을 표시하는 비트] 를 저장하는 2차원 vector를 이용했다.

 

DFS의 풀이과정을 간단히 설명하면 

 

DFS 함수는 DP[N][visited] 배열 값을 return 한다.

 

만약 DP[N][visited]가 탐색된 적이 없다면 N번째 마을을 제외한 prevVisited를 만든다.

여기서 prevVisited = visited - (1<<N)이다.

 

그러면 DP[N][visited]를  DFS(마지막 방문한 마을 M,  prevVisited) + [M에서 N으로 이동하는 비용] 으로 표현할 수 있다.

이 중 가장 작은 값을 DP[N][visited]에 저장하면 된다.

 

+ 여기서 중요한 점이 있는데, 비용이 0인 경우에는 이동할 수 없는 경우다.

그렇기 때문에 특정 마을들만으로는 방문할 수 없는 경우가 생길 수 있는데, 이 경우는 DP[N][visited] = -1로 고려할 수 없는 경우를 체크해 주었다.

 

 

 

 

​

[아이디어 정리]

1. 비트 마스킹을 이용하기 위해  [직전에 방문한 마을][방문한 마을을 표시하는 비트] 를 저장하는 2차원 vector를 만든다.
2.  [직전에 방문한 마을][방문한 마을을 표시하는 비트]의 최적 값이 계산 된 적이 있다면 그 값을 return하고, 만약 계산된 적이 없다면 계산을 하는 DFS 함수를 만든다.
3. 최종적으로 비용이 가장 적은 값을 출력한다.

 

 

 

Code

 

 

#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <set>
#include <algorithm>
#include <queue>
using namespace std;
const int INF = 1987654321;

int DFS(int nowN, int visited, vector<vector<int>>& DP, vector<vector<int>>& graph, int& N) {
	// nowN은 마지막으로 방문한 노드
	int* retV = &DP[nowN][visited];
	if (*retV != INF) {
		return *retV;
	}

	int visitV;

	// 현재 마지막으로 방문한 마을이 N이므로 이전에는 N을 방문하지 않아야 한다.
	int prevVisited = visited - (1 << nowN);

	for (int i = 1; i < N; i++) {
		visitV = 1 << i;
		if ((visitV & prevVisited) != 0) {
			//visitV는 이전에 방문한 마을이 될 수 있다.
			if (graph[i][nowN] != 0) {
				int tmp = DFS(i, prevVisited, DP, graph, N);
				if (tmp != -1)
				{
					*retV = min(*retV, tmp + graph[i][nowN]);
				}
			}
		}
	}
	if (*retV == INF) {
		*retV = -1;
		//경로가 없음을 갱신
	}
	return *retV;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int N;
	cin >> N;
	vector<vector<int>> graph(N, vector<int>(N));
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> graph[i][j];
		}
	}
	vector<vector<int>> DP(N, vector<int>((1 << N), INF));
	int minV = INF;

	for (int i = 1; i < N; i++) {
		if (graph[0][i] == 0) {
			DP[i][(1 << i)] = -1; //경로가 없음
		}
		else
		{
			DP[i][(1 << i)] = graph[0][i];
		}
	}

	int tmp;
	for (int i = 1; i < N; i++) {
		if (graph[i][0] != 0)
		{
			tmp = DFS(i, (1 << N) - 2, DP, graph, N);
			if (tmp != -1) {
				minV = min(minV, tmp + graph[i][0]);
			}
		}
	}
	cout << minV;
	return 0;
}

 

---

BFS가 익숙해서 처음에는 BFS로 풀었지만, 이 경우 queue에 넣거나 체크하는 과정이 생각보다 오래 걸려서 DFS로도 풀어봤다.

DFS로 바꿔서 풀려니 생각보다 바꾸는게 힘들었다;;

예전에 비트 마스킹으로 풀 수 있는 걸 알아도 나중에 풀어봐야지 하고 미뤘던 걸 최근에 푸니까 감회가 새롭네...

 

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