[BOJ] 2098 외판원 순회

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

2098번: 외판원 순회

 

TSP 문제는 학교에서 배웠지만 실제로는 처음 풀어본다.

hueristic 알고리즘으로 NN(Nearest Neighbor)도 배웠던 기억이 있다.

 

시작점에 대해서 고민해봤는데 어차피 circuit이 생기니까 어디서 시작하는지는 중요하지 않았다...ㅋ

입력을 보니 Floyd가 생각나서 이걸 쓸 수 있을까도 생각해봤지만 이 문제랑 관련은 1도 없었다.

고민해보다가 잘 모르겠어서 강의자료를 다시 쳐다봤는데 거기선 집합을 쓴다.

그런데 집합 관련으로는 union-find밖에 모르고 이 문제에 적용하기엔 영 아닌거 같았다.

다른 사람들의 풀이를 참고해보니 비트마스킹으로 해결하더라.

비트는 학교에서 많이 봐서 비트마스킹 자체는 어색하지 않았지만 사용하는 것이 익숙하지 않았다.

 

#include <iostream>
#include <cstring>

#define INF 987654321

int N;
int W[16][16];
int D[16][1 << 16];

int min(int a, int b) {
	return a < b ? a : b;
}

int TSP(int cur, int visited) {
	int& ret = D[cur][visited];

	if (ret != -1) return ret;

	if (visited == (1 << N) - 1) {
		if (W[cur][0] == 0) return INF;
		else return W[cur][0];
	}

	ret = INF;

	for (int i = 0; i < N; i++) {
		if (visited & (1 << i) || W[cur][i] == 0) continue;
		ret = min(ret, TSP(i, visited | 1 << i) + W[cur][i]);
	}

	return ret;
}

int main() {
	std::cin >> N;

	for (int i = 0; i < N; i++) 
		for (int j = 0; j < N; j++) 
			std::cin >> W[i][j];
	
	memset(D, -1, sizeof(D));

	std::cout << TSP(0, 0b0000000000000001);

	return 0;
}

 

후기) 

다른 사람들이 int& ret 같이 사용하길래 나도 한번 써봤는데 실수를 줄일 수 있는 좋은 방법인 것 같다.

memset이랑 비트마스킹에 익숙해져야겠다.