급하게임개발

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

이 문제는 내가 처음 접한 외판원 순회 문제이다 처음에는 브루트포스와 백트래킹을 사용하여 모든 경우의 수를 돌면서 최소의 값을 출력하려고 했으나 시간복잡도가 오바가 될것으로 판단되어 다른사람들의 풀이를 보니 비트마스킹과 dp를 조합하여 이미 방문한  노드의 대해서는 검사하지 않는 다는 것을 파악한 상태로 알고리즘을 구현하였다.

int n, map[16][16];
int dp[16][1 << 16];

n은 우리가 input 받을 노드의 수다
그리고 dp 배열에 우리는 [1<<16]을 해주는데  이것의 의미는 0번 부터 15번을 방문 하지 않았다고 초기화 시켜 놓는 것이다

우리는 깊이 우선 탐색을 통해 해당 알고리즘을 풀것이다 자 이런 외판원 문제는 무조건 사이클을 갖고 있다 그럼으로 어느 한지점을 start 및 Endpoint로 잡아도 값이 똑같이 나온다 필자는 0을 StartPoint를 두고 풀겠다

    if (visit == (1 << n) - 1) { //탐색 완료
        if (map[cur][0] == 0) //이동불가능
            return INF;
        return map[cur][0];
    }

자 이조건 부터 보자 visit의 값 즉 우리가 어느 노드를 방문했는지를 나타내는 visit값이 2의 n승 -1은 n-1 번까지 다 1이된다 즉 0부터  n-1  노드까지 n개의 노드를 다 방문 했다는 것을 의미한다 다 방문했는데 map[cur][0]은 0번으로 돌아갈수 있는 길이 없다는 것을  의미한다. 이럴경우 이동이 불가능 하다

자 이조건을 통과한후

    if (dp[cur][visit] != -1) 
        return dp[cur][visit];

이 조건을 보자 이조건의 의미는 이미 방문한 상태값을 가지고 이미 탐색한적이 있으면 더이상 탐색하지 않는다는 얘기다
즉 우리가 이전에 dp를 초기화 -1 로 초기화 시켜놓았는데 dp[cur][0101] 이 -1이 아니면 우리는 0번과 2번을 방문한 상태에서의 dfs를 돌렸다는 얘기이다 이때 우리는  이를 다시 할 필요 없으므로 해당 값을 return 해준다  자 여기 까지 왔으면

    for (int i = 0; i < n; i++) {
        if (map[cur][i] == 0) //길 X
            continue;
        if ((visit & (1 << i)) == (1 << i)) //이미 방문
            continue;
        dp[cur][visit] = min(dp[cur][visit], map[cur][i] + dfs(i, visit | 1 << i));
    }

이 로직이 남았다 이 로직의 경우 현재 어디어디를 방문하고 현재 내위치에서 갈수 있는 영역을 탐색한다.
visit값을 통해 내가 앞으로 나아가야할 곳이 이미 내가 방문했다면 그 위치를 더 방문할 필요가없으니 continue를 한다
그후에는 min을 통해  현재까지 내가 찾은 최솟값과, 지금 내위치에서 다음위치로 갈 비용 + 다음 위치에서 찾은 min 값을 받으므로서  최솟 값을 갱신 해준다

전체 코드는 아래와 같다

#include <iostream>
#include <cstring>
using namespace std;
int n; int dp[16][1 << 16];
int map[16][16];
#define INF 987654321
int dfs(int cur, int visit) {
	if (visit == (1 << n) - 1) {
		if (map[cur][0] == 0) {
			return INF;
		}
		return map[cur][0];
	}

	if (dp[cur][visit] != -1) {
		return dp[cur][visit];
	}

	dp[cur][visit] = INF;

	for (int i = 0; i < n; i++) {
		if (map[cur][i] == 0)
			continue;
		if ((visit & (1 << i)) == (1 << i))
			continue;
		dp[cur][visit] = min(dp[cur][visit], map[cur][i] + dfs(i, visit | (1 << i)));
	}
	return dp[cur][visit];
}
int main() {
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
		}
	}
	memset(dp, -1, sizeof(dp));
	cout << dfs(0, 1);
}