Search
Duplicate
🍋

외판원 순회

주차
11
문제번호
2098
언어
티어
골드
유형
DP
nj_Blog
nj_상태
이해도
풀이
풀이 O
사람
이해도 2
13 more properties

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++
복사