BOJ2098/ C++

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

2098번: 외판원 순회

백준 온라인저지 2098번 문제입니다. 

비트마스크, DP를 이용해서 풀었습니다.

TSP라고도 부르는데요

문제 자체가 TSP인 문제입니다.

#include<iostream>
#define INF 987654321
#define MAX 16

using namespace std;

int dp[1 << MAX][MAX];
int arr[MAX][MAX];
int n;
void Input() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
		}
	}
}

//visit 방문한 도시에 대한 비트 마스킹
//current 이번에 지날 도시
int TSP(int visit, int current) {

	//current번 도시 방문 추가 
	visit |= (1 << current);

	if (visit == (1 << n) - 1) {
		if (arr[current][0]) {
			return arr[current][0];
		}
		return INF;
	}


	//dp 개념 적용
	if (dp[visit][current] > 0)
		return dp[visit][current];
	dp[visit][current] = INF;

	for (int i = 0; i < n; i++) {

		//current -> 아직 방문하지 않은 i번 도시 가는 경로가 있는 경우
		if (i != current && (visit&(1 << i)) ==0 && arr[current][i] > 0) { 

			//최소 비용 갱신
			int temp = TSP(visit, i) + arr[current][i];
			if (dp[visit][current] > temp)
				dp[visit][current] = temp;

		}
	}
	return dp[visit][current];
}

void solution() {
	int sol = TSP(0, 0);
	cout << sol;
}

int main(void) {
	Input();
	solution();
}

아이디어

TSP 대표문제임

TSP는 브루트포스랑 아주 비슷하다는 느낌을 받는 것 같은데 완전히 이해하는데는 시간이 좀 걸렸던 것 같음

재귀를 이용하였고 1 2 3 4번 도시를 모두 방문 해야한다고 했을때 방문했을때를 1 방문하지 않았을때를 0으로 하여

4비트로 0000 1111 0101 1010과 같이 표현할 수 있음 
재귀를 이용하여 각각의 도시를 모두 방문해야할때 최소비용을 찾아야함 -> 모두 확인해봐야함

아래는 코드에서 visit의 비트는 아래와 같이 바뀌는데 손으로 풀면서 가장 이해를 도왔던 다이어그램임

 

0001 ->  0011  -> 0111 -> 1111

                     -> 1011 -> 1111

       ->  0101  -> 0111 -> 1111

                     ->1101 -> 1111

       ->  1001  -> 1011 -> 1111

                    -> 1101 -> 1111