Memo
이번문제는 해결 방법에 필요한 방법인 비트마스킹을 모르고 있어서 해당 부분을 정리하느라 가장 시간이 오래 걸렸다. 비트마스킹을 사용하면 특정 노드를 방문처리해야하는 경우 쉽게 표현할 수 있다.
예를들어, {1, 2, 3, 4, 5} 라는 노드가 있다. 여기서 우리가 1번 부터 순서대로 5번노드까지 지나간다면 기존에는 아래와 같이 방문체크를 해주었다.
visited = {1}
visited = {1, 2}
visited = {1, 2, 3}
visited = {1, 2, 3, 4}
...
C
복사
한 칸을 방문한 경우를 체크하는 경우 단일 배열로 가능하지만, 방문한 모든 노드를 체크해야한다면 우리는 엄청난 배열을 선언해야한다.
visited[1][1][1][1][1];
// 만약 1,3,5를 방문했으면
// visited[1][0][1][0][1] = 1;
C
복사
하지만 2진수를 활용해 더욱 더 효율적으로 방문노드를 표현할 수 있다. 예를들어 1, 3, 5를 방문했으면 10101(2)로 표현할 수 있다. 즉, 5개의 노드의 모든 방문처리를 00000 ~̆̈ 11111(2) 으로 표현할 수 있는 것이다.
visited[11111(2)] = visited[63];
C
복사
이제 여기까지는 알겠는데 도대체 저 visited[]안에 어떻게 2진수를 집어넣을 수 있는지 궁금했다. 생각보다 간단했다. 배열 인덱스를 참조하는 대괄호 안에 비트 연산을 사용해서 집어넣으면 되는 것이었다.
int main()
{
int arr[8];
arr[1 << 0] = 1;
arr[1 << 1] = 2;
std::cout << "arr[1] : " << arr[1] << std::endl;
std::cout << "arr[2] : " << arr[2] << std::endl;
}
C
복사
만약 우리가 1, 3, 5번 노드 방문처리를 하고 싶다면 아래와 같이 하면 된다.
int main()
{
int dp[(1 << 5) - 1]; // dp[63]과 같은 의미이다!
int visited = 0;
visited = visited | (1 << 1);
visited = visited | (1 << 3);
visited = visited | (1 << 5);
dp[visited] = val;
}
C
복사
이제 이 비트마스크를 기반으로 아래 문제를 해결해 볼 예정이다.
외판원 문제는 TSP문제이다....
너무 잠와서 내일해야겠돠..
Code
제출 날짜
@2/16/2021
메모리
6636 KB
시간
32 ms
#include <iostream>
#include <vector>
int N;
int MAX = 9999999;
std::vector<std::vector<int> > map;
std::vector<std::vector<int> > cache;
void input()
{
std::cin >> N;
map = std::vector(N, std::vector(N, 0));
cache = std::vector(N, std::vector(65536, MAX));
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
std::cin >> map[i][j];
}
int tsp(int cur, int visited)
{
if (visited == (1 << (N)) - 1)
{
if (map[cur][0] > 0)
return map[cur][0];
return MAX;
}
if (cache[cur][visited] == MAX)
{
for (int i = 0; i < N; i++)
{
//std::cout << "방문노드 : " << visited << std::endl;
if ((visited == (visited | (1 << i))) || !map[cur][i])
continue;
cache[cur][visited] = std::min(cache[cur][visited], tsp(i, visited | (1 << i)) + map[cur][i]);
}
}
return cache[cur][visited];
}
void solution()
{
std::cout << tsp(0, 1);
}
void preset()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);
}
int main()
{
preset();
input();
solution();
}
C++
복사
