Memo
•
문제 접근
우선 처음 문제를 읽고나서 든 생각은, 어떻게 visited 체크를 하느냐 였습니다. 또한 dp를 사용하지 않으면 O(N!)의 시간복잡도를 갖기 때문에 dp를 통해 문제를 해결해 나가야한다는 것을 인지하고 있었습니다. visited체크를 tsp 로직 함수마다 풀어줘 버리면 체크하는 의미가 없기 때문에 풀어주지 않겠다는 생각이 들었습니다. 그러므로 재귀적으로 특정 조건들에 의해서 다음 노드로 들어간 후에 그 노드에서 갈 수 있는 가장 짧은 길을 dp 배열에 넣으면 되겠다는 생각이 들었습니다. 하지만 여전히 visited를 어떻게 설정해야 할지 감이 오지 않았습니다.
•
visited
visited 체크 기법을 스스로 터득했으면 좋았겠지만, 아이디어가 도저히 생각이 나지 않아서 구글링을 했습니다. 비트마스크로 visited 체크를 할 수 있다는 것을 알게 되었습니다. 일단 그 사실을 알고 나서 문제에 접근했습니다. 메모리 측면에서는 N이 16까지 이기 때문에 2의 16승인 65536이므로 int의 크기인 4를 곱해도 여유롭다는 생각이 들었습니다. 또한 비트마스크로 visited를 표현을 하면 굉장히 편리하겠다는 생각을 했습니다.
•
점화식
dp[N][visited] = std::min(dp[N][visited], tsp(next, next + visit) + W[cur][next]);
위 점화식을 보고나서는 visited 체크배열을 따로 두는 것이 아닌 비트 연산을 통해 dp 배열 인덱스로 들어간다는 사실을 알게되었습니다. 위 visited 파트에서 계산한 메모리에 N인 16을 곱해도 (16 * 65536 * 4 ) 메모리는 여유롭기 때문에 해당 점화식을 어떻게 코드로 녹여내느냐가 관건이었습니다.
•
문제 해결
위의 점화식을 보고나서 @suhshin과 함께 토론해 가며 문제를 풀었습니다.
1.
tsp 함수 만들기
solution 부분에서는 모든 노드를 조사하면서 각 노드들을 tsp 함수의 첫 번째 인자로 넣고, visited 체크를 두 번째 인자로 넣는 방법을 생각했습니다. tsp 내부에서는 visited를 통해 방문 했는지를 확인했어야 합니다.
2. visited에 대한 이해
visited를 어떻게 표현해야할지에 대한 감을 잡았습니다.
0 0 0 0
4번 3번 2번 1번 << 각 노드별로 비트를 줍니다. 0인 경우 아직 방문 전.
0 0 0 1
4번 3번 2번 1번 << 다음과 같은 경우는 1번 노드를 방문했다는 뜻 입니다.
위를 표현하기 위해서는 shift 연산이 필요했습니다. tsp 첫 번째 인자로 노드를 넣는다고 했는데, tsp 함수 내부로 들어왔을때 해당 매개변수는 current node 입니다. tsp 함수 내부로 들어온 순간, 해당 노드로 들어왔다고 생각하면 됩니다. 따라서 visited를 전달해 줄때, 1 << current 를 통해 현재 자신이 어디를 방문할 지를 체크해 줘서 넘겨주면 됩니다.
3. dp[cur][visited]에 대한 이해
이 부분은 처음에는 명확히 설명이 잘 안됐습니다. 지금 정리하는 입장에서 결론을 말씀드리면, cur는 현재 자신이 속해있는 노드번호를 의미하고, visited는 자신이 속해있는 노드번호를 포함해서 현재 자신이 어떤 경로를 통해서 왔느냐가 기록되어 있습니다.
이때 추가적으로 @suhshin과 얘기를 통해 깨달은 사실이 있습니다.
n이 6이라고 가정하고 current node가 6 이라고 가정하겠습니다.
1 → 3 → 5 → 4 를 비트로 표현하면 011101이고,
1 → 4 → 5 → 3 을 비트로 표현해도 011101인데 과연 visited 체크를 중간에 풀어야 하느냐에 대한 의문이 들었는데 결국에는 dp[6][011101]을 구해 놓으면 그 다음 방문할 노드들은 위 아래 모두 동일하므로 visited 체크는 풀지 않고 dp[6][011101]에 값이 존재한다면 그 값을 그대로 이용하면 된다는 결론을 내렸습니다.
4. visited 체크
tsp 함수 내부에서 다음 이동할 노드를 정하면 되는데, 이는 반복문을 통해서 1 부터 N 까지 조사하면 됩니다. 이때 분기문이 필요하다는 느낌이 팍 듭니다. Weight가 0인 경우는 해당 경로는 없는 것이기 때문에 그 부분을 조건으로 걸러주면 되고, visited 체크를 방문하고 나서 하지 않고 체크를 한 후에 넘겨주는 방식을 택했기 때문에 그 부분에 대한 조건이 필요했습니다. 그 부분은 크게 어렵지 않았는데, visited와 다음 visited가 동일하면 이미 방문한 것이기 때문에 그 조건을 넣어주면 됐습니다. 다음 visited는 현재 visited와 ( 1 << 다음 노드)를 or 연산한 것으로 계산해 낼 수 있습니다.
5. 점화식 넣기
위의 점화식을 넣기 위해서 생각해야 할 부분이 있었는데, 리턴값을 어떻게 설정하느냐 였습니다. 결론은 어렵지 않게 나왔는데, dp[cur][visited]에서의 cur와 visited는 이전에서 넘어온 값이므로 이곳에는 무조건 이 경로로 갈 경우의 최소값이 들어가있어야 하고, 리턴값 역시 이 값을 리턴해 주면 됩니다. 따라서 리턴은 dp[cur][visited]로 둡니다.
6. 다시 원래 노드로 돌아올 경우를 어떻게 체크할 것인가
결론적으로 이 윗 부분까지는 모두 맞았는데, 이 부분이 문제였습니다.
처음에 @suhshin과 이 부분에 대한 디테일이 부족해서 해결방법에 대해 고민을 했는데, 처음 내린 결론은 dp[시작][11111111...] 을 출력하면 된다였습니다. 하지만 저희가 구현한 방식은 처음 방문을 한 dp 배열에 저장된 값으로 누적합을 받는 것이기 때문에, 이 방법은 통하지 않았습니다.
만약 visited가 11111..로 모두 방문했다고 한다면, 맨 처음 노드로 돌아가야합니다. 그것에 대한 weight는 함수를 리턴한다 하더라도 저장되지 않기 때문에 무조건 리턴값으로 지정해 주어야 합니다. 또한 solution 부분에서 처음 시작 지점을 전역변수로 저장해 놓음으로써 자신이 어디서부터 시작되었는지를 알 수 있게 해줘야 합니다.
이 부분에서 의문이 들었던 것은, 방문 체크를 하고 넘겨주는 것이 아니라 tsp 함수 내부에서 방문 체크를 해주면 어떻게 되는가 였는데 그렇게 구현을 할 경우에도 역시 맨 처음의 노드를 알고 있어야 하기 때문에 결론적으로 전역변수 또는 인자로 값을 전해주면 해결될 문제였습니다. (사실 이 글을 정리하기 전까지는 함수로 넘겨줄때 visited를 체크하고 넘겨주면 안된다고 생각했는데, 함수 내부로 들어와서 처음에 visited체크를 해줘도 될 것이라는 생각으로 바뀌었습니다.)
7. solution 부분에서 모든 노드를 조사해야 하는가
결론적으로 외판원 문제는 어떤 정점에서 출발하든지 간에 최솟값은 동일하므로 solution 부분에서 모든 노드를 확인할 필요는 없습니다. 처음에 새로운 노드를 조사할 때마다 결과값이 다르게 나와서 코드가 틀린줄 알고 좌절하고 있다가 제출했는데 맞아서 운이 좋았다 생각했는데, 나중에 @suhshin과 얘기를 나눈 결과 dp 배열을 초기화를 시키지 않고 그대로 돌려서 생긴 문제였습니다. 왜냐하면 방문을 모두 해서 11111...1 이 된 경우에 맨 처음에 시작한 노드로 돌아가야 하는 weight값이 추가적으로 필요하게 되는데, 그 값이 처음 시작 노드가 바뀔때마다 달라지기 때문이었습니다. dp를 초기화 하는 구문을 넣으니 모든 노드에서 동일한 결과값이 나왔습니다.
•
처음 @suhshin과 함께 칠판에 작성한 pseudo code
Code
제출 날짜
@2/24/2021
메모리
6700 KB
시간
28 ms
#include <iostream>
#include <vector>
#include <algorithm>
size_t N;
std::vector<std::vector<int> >W;
std::vector<std::vector<int> >dp;
int r;
void input_faster()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
}
void input()
{
input_faster();
std::cin >> N;
W.resize(N + 1, std::vector<int>(N + 1, 0));
for (size_t i = 1 ; i <= N ; i++)
for (size_t j = 1 ; j <= N ; j++)
std::cin >> W[i][j];
dp.resize(N + 1, std::vector<int>((1 << N) - 1 , 1 << 30));
}
int tsp(int cur, int visit)
{
if (visit == (1 << N) - 1)
{
if (W[cur][r])
return (W[cur][r]);
return (1 << 30);
}
if (dp[cur][visit] == (1 << 30))
{
for (size_t i = 1 ; i <= N ; i++)
{
if ((visit == (visit | (1 << (i - 1)))) || !W[cur][i])
continue;
dp[cur][visit] = std::min(dp[cur][visit], tsp(i, visit | (1 << (i - 1))) + W[cur][i]);
}
}
return (dp[cur][visit]);
}
void solve()
{
r = 1;
std::cout << tsp(1, 1);
}
int main()
{
input();
solve();
return (0);
}
C++
복사
