[순열][재귀] 외판원 순회 2 10971

외판원 순회 2 (10971)

 

풀이코드

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;
// 10971 외판원 순회 2
const int INF = 123456789;
int n;
int board[10][10];
int minSum = INF;

int getCost(vector<int> &vec){
	int sum = 0;
	for(int i = 0; i < n; i++){
		// 갈 수 없다면 즉, 비용이 0 이라면 inf 를 return
		if(board[ vec[i % n] ][ vec[(i + 1) % n] ] == 0) return INF;
		else{
			sum += board[  vec[i % n] ][ vec[(i + 1) % n] ];
		}
	}
	
	return sum;
}

void solve(vector<int> &vec){
	// 비용 구하기
	int cost;
	cost = getCost(vec);
	if(cost != INF){
		minSum = minSum > cost ? cost : minSum;
	}
	
	if(next_permutation(vec.begin() + 1, vec.end())) {
		solve(vec);
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); 
	cout.tie(nullptr); 
	
	cin >> n;
	
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			cin >> board[i][j];
		}
	}
	
	vector<int> city;
	// 도시의 번호를 오름차순으로 정렬하여 넣어둠.
	for(int i = 0; i < n; i++) city.push_back(i);
	solve(city);
	cout << minSum << '\n';
	
}

 

해설

---

적용한 레시피 / 방법론 + 접근법

1

풀이

1. 경우의 수 계산해보기

- 도시가 최대 10개. 도시를 어떠한 순서로 방문해야 하므로 최대 경우는 10! . 브루트 포스로 충분히 가능하다.

2. 브루트 포스 구현

- 도시의 번호로 모든 순열을 구현해본 뒤 각 순열에서의 비용을 구하여 최솟값을 찾는다.

3. 처음 도시로 돌아오는 경우

- 0번 -> 1번 -> 2번 -> 3번 을 순회했다면 원래 도시인 0번 도시로 돌아와야 한다. 이 부분의 구현을 마지막에 더해주는 형식으로 할 수도 있지만, for 문을 돌 때, index 를 % n 을 이용한다면 번거로움 없이 한번에 구현해낼 수 있었다.

아쉬웠던 부분 / 오답 원인 / 개선해야 할 점

1. 문제를 세세히 읽지 않음.

- 처음 도시로 돌아오는 경우를 처음에 구현할 때 빼먹고 했었다. 문제를 잘 읽자

2. INF 의 사용 미숙

- INF 를 사용할 때, min 을 구하는 문제이므로 INF 를 양의 최대로 설정했어야 하는데, 멍청하게 음의 최대로 설정하여 답을 이상하게 도출했었다.