백준) 9520 NP-hard (PUTNIK)

9520. NP-hard

문제

TSP는 매우 유명한 문제이다. 이 문제는 NP-hard 문제이기 때문에 효율적인 해법이 존재하지 않는다. 이번에는 약간 변형된 TSP 문제를 풀어보자.

TSP문제는 도시 N개를 모두 한 번씩 방문하는 문제이다. 도시는 1번부터 N번까지 번호가 붙여져 있다. 각 도시 사이의 거리는 모두 알려져 있으며, 모든 도시를 방문하는데 드는 시간을 최소로 해야 한다.

번호가 K인 도시를 방문하려면, K보다 작은 번호를 가진 모든 도시를 K번을 방문하기 전에 모두 방문하거나, 방문한 후에 모두 방문해야 한다. 즉, K보다 번호가 작은 도시 중 하나를 K번 이전에 방문하고, 다른 하나를 K번 이후에 방문하면 안된다.

위의 조건을 만족하면서 모든 도시를 방문하는데 드는 시간의 최소값을 구하는 프로그램을 작성하시오. 첫 도시와 마지막 도시는 같지 않아도 되며, 어느 도시에서 시작하고 마쳐도 상관없다.

입력

첫째 줄에 도시의 수 N (2 ≤ N ≤ 1500)이 주어진다.

다음 N개 줄에는 [0, 1000] 구간에 포함되는 양의 정수가 주어진다. A번째 행의 B번째 숫자는 A에서 B로 가는데 필요한 시간이고, 이 수는 B번 행의 A번째 숫자와 같다. A와 B가 같은 경우에는 0이 주어지며, 이외의 경우에는 항상 양의 정수이다.

출력

첫째 줄에 문제의 조건을 만족하면서 모든 도시를 방문하는데 드는 시간의 최소값을 출력한다.

예제 입력 

3
0 5 2
5 0 4
2 4 0

예제 출력 

7

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

1. 접근

모든 도시들은 서로 연결되어 있고, 일련의 규칙으로 모든 도시를 방문해야 한다. 모든 경우 중에 최소 비용을 구해야 한다.

이 일련의 규칙이란

1) k도시를 방문하려면 k보다 작은 도시들을 전부 미리 방문했거나,

2) k를 방문한 이후 딴짓 하지 말고 k보다 작은 모든 도시들을 이후에 방문해야 한다.

따라서 도시가 1, 2 두 개라면,

[1->2] 혹은 [2->1] 이 가능하다.

도시가 3까지 있다면,

[1->2->3] 혹은 [3->1->2] 혹은 [3->2->1] 혹은 [2->1->3] 이 가능하다

[1->3->2] 순서는 3을 방문하려고 했는데, 2번 규칙에 의하면 1도시를 먼저 방문해버렸기 때문에 옳지 않은 방법이다.

[2->3->1] 순서는 2번 규칙에 의하면 2도시를 방문했으면 딴짓 하지 말고 작은 도시를 방문해야 하지만

3도시로 가버렸으므로 옳지 않은 방법이다.

이와 같은 방문순서들을 n이 주어졌을 때 만드는 패턴이 있지 않을까?

만약 그렇다면 우리는 빠르게 만들어진 순서들을 시도해보는 다이나믹 프로그래밍을 할 수 있을 텐데!

2. 풀이

패턴은 다음과 같다

먼저 1을 시퀀스에 추가한다.

그 다음 2를 시퀀스의 왼쪽이나 오른쪽에 추가한다.

그 다음 3을 시퀀스의 왼쪽이나 오른쪽에 추가한다.

...

위의 패턴으로 우리는 규칙을 만족하는 모든 방법을 만들어 낼 수 있다.

귀납적으로 증명해보자.

1) 1밖에 없는 시퀀스는 규칙을 만족한다.

2) n까지 위의 패턴으로 만든 시퀀스가 규칙을 만족한다고 가정해보자.

3) n+1 도시를 왼쪽이나 오른쪽에 추가해도 규칙을 만족한다면 우리의 패턴은 참이다.

2단계 까지 이뤄진 시퀀스의 가장 번호가 큰 도시는 당연히 n도시다.

이제 3단계에서 n+1 도시를 왼쪽에 추가한다고 하면, 우리는 규칙 2를 만족하는 방문순서를 만들어 낸것이다.

반대로 오른쪽에 추가한다고 하면, 이 시퀀스는 규칙 1을 지키는 방문순서가 될 것이다.

이제 패턴에 따라 모든 경우를 계산해 줄 함수를 정의해보자.

func(현재 시퀀스의 왼쪽 도시 번호, 현재 시퀀스의 오른쪽 도시 번호, 추가할 도시 번호)

= 현재 상황에서의 만들 수 있는 종래의 최소비용 = func(int x, int y, int num)

기저사례는 num이 n+1까지 확장될 경우다. 더 이상 추가할 도시가 없다.

이 도시 num을 왼쪽에 추가한다면, 시퀀스의 왼쪽은 num이 될 것이므로,

func(num, y, num+1) + dist[x][num] 

이 도시 num을 오른쪽에 추가한다면, 시퀀스의 오른쪽은 num이 될 것이므로,

func(x, num, num+1) + dist[y][num]

두 경우를 계산해보고, 둘 중 작은 값이 정답이다. 메모이제이션으로 O(n*n).

3. 코드

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
 
int dp[1501][1501];
int dist[1501][1501];
int n, i, j;
 
int func(int x, int y, int num) {
    if (num == n + 1)
        return 0;
 
    int& ref = dp[x][y];
    if (ref != -1)
        return ref;
 
    int left = func(num, y, num + 1) + dist[x][num];
    int right = func(x, num, num + 1) + dist[y][num];
 
    return ref = min(left, right);
}
 
int main() {
    scanf("%d", &n);
    for (i = 1; i <= n; ++i)
        for (j = 1; j <= n; ++j)
            scanf("%d", &dist[i][j]);
 
    memset(dp, -1, sizeof(dp));
 
    printf("%d", func(1,1,1));
 
    return 0;
}

4. 후기

패턴을 못찾았다면 난리 필 문제