C++ / 백준 / 10971 / 외판원 순회2

문제

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

10971번: 외판원 순회 2

 

문제풀이

DFS로 풀었고, 1차원 방문 벡터를 이용한다.

처음에 출발하는 도시, 현재 위치한 도시, 비용, 방문 배열을 인자로 받는 함수 Move를 만든다.

Move는 매번 방문 벡터를 돌면서 가지 않은 도시가 있는지 체크를 한다.

모든 도시를 돌았고, 현재 있는 도시가 처음에 출발한 도시였고, answer값 보다 작으면 answer값을 경신한다.

가지 않은 도시가 있다면 다음 도시를 간다면 발생하는 비용이 answer보다 적은 지, 비용이 0이어서 갈 수 없는 경우인지를 판별하고, 갈 수 있다면 다음 도시로 간다.

 

 

코드

#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>>value;
int answer = 1e9;
int N;

void Move(int start, int node, int cost, vector<bool>visit) {
	if (cost != 0)	visit[node] = true;
	int idx = 0;
	int visit_count = 0;

	for (idx = 0; idx < N; ++idx) {
		int next_cost = cost + value[node][idx];
		if (visit[idx]) visit_count++;
		else if (!visit[idx] && next_cost < answer && value[node][idx] != 0)
			Move(start, idx, next_cost, visit);
	}
	if (visit_count == N && node == start)
		answer = min(answer, cost);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int y = 0, x = 0;
	cin >> N;
	value = vector<vector<int>>(N, vector<int>(N, 0));
	for (y = 0; y < N; ++y)
		for (x = 0; x < N; ++x)
			cin >> value[y][x];

	vector<bool>visit(N, false);

	for (y = 0; y < N; ++y)
		Move(y, y, 0, visit);
	cout << answer;
}