[백준 BOJ][C++]10971번 원판원 순회2 풀이: DFS or next_permutation()

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

10971번: 외판원 순회 2

 

 이 문제는 DFS 또는 next_permutation() 함수를 사용해서 해결할 수 있습니다. 

 

 dfs로 아직 방문하지 않은 도시를 방문하는 과정은 순열을 만드는 과정과 동일한데요!

 

 때문에 dfs를 직접 구현해도 되지만 next_permutation() 함수로 좀 더 쉽게 해결할 수 있습니다.

 

[풀이 과정]

1. 도시 0번부터 n-1번까지 dfs를 호출

2. 아직 방문하지 않은 도시에 대해 이전 도시 prev와의 비용이 0이 아니라면 dfs 호출

3. depth가 n이라면 마지막 도시와 시작 도시간의 비용을 sum에 더하고 종료

3. 모든 경로를 탐색할때까지 반복

 

 

 

[ DFS 풀이 ]

#include<iostream>
#include<algorithm>
#include<array>
#include<vector>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<string>

using namespace std;

#define MAX 100000000;

int n;
int w[11][11];
int ans = MAX;
bool visit[11] = { false, };

void dfs(int start, int prev, int sum, int depth) {
	if (depth == n && w[prev][start] != 0) {
		sum += w[prev][start];
		ans = min(ans, sum);
		return;
	}

	for (int i = 0; i < n; i++) {
		if (!visit[i] && w[prev][i] != 0) {
			visit[i] = true;
			dfs(start, i, sum + w[prev][i], depth + 1);
			visit[i] = false;
		}
	}
}

int main(void) {

	cin >> n;

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

	for (int i = 0; i < n; i++) {
		memset(visit, false, sizeof(visit));
		visit[i] = true;
		dfs(i, i, 0, 1);
	}

	cout << ans;

	return 0;
}

 

[ next_permutation() 풀이 ]

#include<iostream>
#include<algorithm>
#include<array>
#include<vector>
#include<cmath>
#include<cstdlib>
#include<string>

using namespace std;

#define MAX 100000000;

int n;
int w[11][11];
vector<int> num;

int main(void) {

	int ans = MAX;

	cin >> n;

	for (int i = 0; i < n; i++) {
		num.push_back(i);
		for (int j = 0; j < n; j++)
			cin >> w[i][j];
	}
	
	do {
		int sum = 0;
		int start = *(num.begin());
        	bool flag=false;

		for (auto itr = num.begin(); itr != num.end(); itr++)
		{
			int i = *(itr);
			int j;

			if (itr == num.end() - 1) {
				j = start;
			}
			else {
				j = *(itr + 1);
			}
            
            		if(w[i][j] == 0){
                		flag=true;
                		break;
            		}
			sum += w[i][j];
		}

        	if(!flag)
		    ans = min(ans, sum);

	} while (next_permutation(num.begin(), num.end()));

	cout << ans;

	return 0;
}