백준 2098번 _ 외판원 순회

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

2098번: 외판원 순회

 풀이방법

 완전탐색으로 푼다면 16!로 말도안되는 시간이 걸린다. 

 그러므로 dp를 추가해서 적절히 중복되는 연산을 저장하고 그 값을 이용함으로써 연산을 줄이는 방법이 필요하다.

 

 예를 들어

 1 2 3 4 5 6 7

 1 2 3 4 5 7 6

 1 2 3 4 6 5 7

 1 2 3 4 6 7 5

 1 2 3 4 7 5 6

 1 2 3 4 7 6 5

 까지의 연산을 진행했다면, dp[1][1111000]은 이후의 값들중 최솟값을 이미 저장하고 있기 때문에

 1 3 2 4 의 경우에서 더 이상 진행해봤자 중복계산이다. 그러므로 dp[1][1111000]의 값을 return받는다.   

 

 그러니까 dp[현재도시][visited]는 지금까지 왔던 도시들의 최솟값이 아니라 앞으로 갈수있는 모든 경우의 최솟값을 저장한 것이다.   

---

 전체코드

#include <iostream>
#include <algorithm>

#define maxSize 16
#define INF 987654321

using namespace std;

int dp[maxSize ][1 << maxSize];
int W[maxSize][maxSize];
int N, all;

void Input()
{
	cin >> N;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cin >> W[i][j];

	all = (1 << N) - 1;
}

int dfs(int here, unsigned int visited)
{
	//도착시
	if (visited == all)
	{
		if (W[here][0] == 0)
			return INF;
		else
			return W[here][0];
	}

	int& ret = dp[here][visited];
	if (ret != 0) return ret;

	ret = INF;
	for (int there = 1; there < N; there++)
	{
		if (W[here][there] == 0 || visited & (1 << there))
			continue;
		
		visited |= (1 << there);
		ret = min(ret, dfs(there, visited) + W[here][there]);
		visited &= ~(1 << there);
	}
	return ret;
}

int main()
{
	Input();
	cout << dfs(0, 1);
	return 0;
}

---

 후기

눈물나올정도로 이해가 안가는 문제였다. 메모제이션을 어떻게 활용해야할지 아무리 생각해도 떠오르지 않았다.

 ㄹㅇ 빡대가리 인증이다. 그리고 요즘 머리가 너무 안돌아가는거 같다. 매일매일 풀었음에도 불구하고, 오히려 보름전보다 문제 해결능력이 떨어진 느낌이라 서럽다.

 

 슬럼픈가.. 슬럼프일 실력도 없는데ㅠㅠ