외판원 순회

Created

2021/03/23 01:58

문제 번호

2098

카테고리

비트마스킹

2098번: 외판원 순회

외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자. 1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다.

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

Memo

TSP는 대표적인 NP-Hard 문제로, 시간 복잡도는

O(n!)

n

값이

15

이상이면

1

조 이상의 단위로 올라가버림 → 현 문제에서 주어진 최대

n

값인 16에 대해서는 풀지 못함

일반적인 시간 복잡도로는 풀지 못하지만, 순회는 해야하기 때문에 톱니바퀴 문제가 떠오름 (14891번) → 해당 풀이는 순회를 위해 DFS에 비트마스킹으로 풀어서 공간 복잡도 및 시간 복잡도를 많이 줄여서 풀었었음

방문 상태를 비트로 표현하면 되는데,

n

이 최대

16

이므로 4바이트 내의 자료 형으로 충분히 커버 가능

비트를 이용하면 1~4까지 노드가 있을 때 아래와 같이 방문 노드를 표현할 수 있음

0001

0010

0100

1000

→ 위에서 모든 노드 방문은

1111

로 표현되며, 이는

2^4 - 1

과 같음

→ 최대

2^{16}

만큼의 연산량이 필요하기 때문에 비트마스킹 연산에 대해서만

O(2^n)

로 표기 가능하고, 모든 노드 방문은

2^{n} - 1

로 표현할 수 있음

방문 상태 이용만으로 충분한가에 대한 고민을 하게 됨 → 이대로 돌리면 여전히 브루트포스와 다를 것이 없음 (정답이 나오지 않음)

방문 상태와 현재 노드 에 대한 최소 비용이 여러 정답 속에서 중복될 수도 있으므로, 방문 상태와 현재 노드에 대한 최소 비용을 유지할 수 있도록 Memoization 해야함 → 해주지 않으면 시간 초과 가능성이 다분해보임

각 노드에 대한 방문 상태이므로

O(n)

이 추가적으로 요구됨

비트마스킹과 각 노드에 대한 연산이

O(n \times 2^n)

으로 표현되고,

n

이

16

이라고 해도 연산량 내에 해당됨 → DFS 까지 고려하면

O(n^2 \times 2^n)

이 되는데 역시나 연산량 내에 해당함

한 노드를 잡고 정답을 여럿 찾았을 경우, 다른 노드에 대해서도 DFS를 돌려야 하는가? → 그렇지 않음 한 노드에서 나온 정답이 곧 여러 정답과 중복됨 (TSP 경로의 성질)

1

이라는 노드를 시작점으로 잡아서 찾은 여러 정답 중

1 → 2 → 3 → 4 → 1

가 하나의 해일 때,

1→ 2→ 3 → 4 → 1

라는 답이나

2

라는 노드를 시작점으로 잡아서 찾은

2 → 3→ 4→ 1 → 2

나 비용은 동일하다는 것을 알 수 있음

재귀 구조만 잘 잡으면 됨

→ 방문 하지 않았고, 방문이 가능한 (비용이 있는) 경우 방문 비용 + 재귀 호출

→ 이에 따른 재귀 호출의 반환 값은 비용이 되어야 함

→ 최종적으로 원하는 비용 값은 최소 값이므로 재귀 호출로 만든 Sub Problem의 반환 값도 최소 값이어야 함 (즉, 최소 값을 찾을 수 있는 연산이 포함되어야 하는 것)

→ 이렇게 찾아진 Sub Problem의 최소 값도 Memoization에 기록 되어야 함

방문 상태를 나타내는 노드가

2^n

만큼 존재함 → 인덱스

1

부터 두고 사용하는 것보단 최대한 당겨서

0

으로 맞추는 것이

6000

KB 정도의 메모리를 아낄 수 있음

입력으로 받는 비용은 최대

16 \times 16

개만 있으면 됨 → 인덱스

1

부터 두고 사용하는 것보단 최대한 당겨

0

으로 맞추는 것이

200

KB 정도의 메모리를 아낄 수 있음

Code

제출 날짜

@2/24/2021

메모리

6436 KB

시간

28 ms

#include <algorithm>
#include <iostream>
#include <vector>

int		g_n;
int		g_ans;
std::vector<std::vector<int>> g_cost;
std::vector<std::vector<int>> g_dp;

void	pre_setting(void)
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);
}

void	input_action(void)
{
	std::cin >> g_n;
	g_cost = std::vector<std::vector<int>>(g_n, std::vector<int>(g_n, 0));
	g_dp = std::vector<std::vector<int>>(g_n, std::vector<int>(1 << g_n, 0));
	for (int i = 0; i < g_n; i++)
		for (int j = 0; j < g_n; j++)
			std::cin >> g_cost[i][j];
}

int		tsp(int n, int m)
{
	if ((m == (1 << g_n) - 1) && g_cost[n][0])
		return (g_cost[n][0]);
	if (g_dp[n][m])
		return (g_dp[n][m]);
	g_dp[n][m] = 1000000000;
	for (int i = 0; i < g_n; i++)
		if (!(m & (1 << i)) && g_cost[n][i])
			g_dp[n][m] = std::min(g_dp[n][m], g_cost[n][i] + tsp(i, m | 1 << i));
	return (g_dp[n][m]);
}

void	logic(void)
{
	g_ans = tsp(0, 1);
}

void	output_action(void)
{
	std::cout << g_ans;
}

void	solution(void)
{
	input_action();
	logic();
	output_action();
}

int		main(void)
{
	pre_setting();
	solution();
	return (0);
}
C++
복사