[BOJ 17592] Running Routes

문제

---

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

풀이

---

풀다가 정말 울뻔했다.

간선을 아무거나 고르고 나눠진 두 구역에서 부분 문제를 풀면 될 거라 생각했다.

하지만 이 생각만으로는 구현을 할 수 없었다.

예로 들어 N이 20일 때, 1-15 엣지를 택한 후 5-10 엣지를 택하면 2~4번 노드는 11~14번 노드와 연결 가능한데 이를 모두 고려하려면 한도 끝도 없기 때문이다.

재귀 함수의 파라미터로는 부분 문제의 상황을 명시하면서도 메모리를 적당히 잡아먹는 것이어야 한다.

엣지의 연결 상태는 길이 N짜리 배열로 나타낼 수 있지만 메모이제이션을 할 수가 없었고, 비트마스크는 당연히 N이 500이하라서 불가능했다.

조금 더 생각을 해보니, 0번 노드부터 차례로 엣지를 정하고 나중엔 거들떠보지도 않으면 되겠단 생각이 들었다.

그래서 다음과 같은 함수 f를 정의했다.

f(x, y) : x~y번 노드끼리만을 겹치지 않게 연결할 수 있는 최대 엣지 수

def f(x, y):
    if dp[x][y] != -1:
        return dp[x][y]
    
    res = 0
    for i in range(x, y):
        for j in range(i + 1, y + 1):
            if board[i][j]:
                res = max(res, f(i + 1, j - 1) + f(j + 1, y) + 1)
    
    dp[x][y] = res
    return res

이 함수를 이용한 맨 처음 풀이는 TLE가 떴다.

문제의 시간제한이 12초 (추가시간 없음)이었기에, 파이썬에 대한 불신이 살아나며 C++로 그대로 짜봤다.

그랬더니 틀렸습니다가 떴고, 잘못된 부분을 고치니 다시 TLE가 떴다.

Top-Down 방식에서 Bottom-Up 방식으로 고쳐도 봤지만 여전히 TLE여서, 반쯤 울면서 깊은 생각에 잠들었다.

얼마 후 다음과 같은 사실을 알 수 있었다.

f(x, y)에서 i-j 간선이 연결됐다면, i가 j + 1 이상일 땐 무시해도 된다.

i-j 간선이 연결되면 res 값은 f(i + 1, j - 1) + f(j + 1, y) + 1 이상인데, f(j + 1, y) 항이 j + 1-* 간선이 연결됐을 때의 값 이상이기 때문이다.

조금 다르게 얘기해보면, j + 1-* 간선을 연결하는 경우는 x~j번 노드를 무시하는 상황인데 i-j 간선을 고르지 않을 이유가 없다.

def f(x, y):
    if x > y:
        return 0
    
    if dp[x][y] != -1:
        return dp[x][y]
    
    res = 0
    flag = 1000
    for i in range(x, y):
        if i > flag:
            break
        for j in range(i + 1, y + 1):
            if board[i][j]:
                flag = min(flag, j)
                res = max(res, f(i + 1, j - 1) + f(j + 1, y) + 1)
    
    dp[x][y] = res
    return res

그래서 이어진 간선들 중 최소의 j값을 의미하는 flag 변수를 만들어, i가 flag를 넘어가면 break하도록 했다.

결국 AC를 받아냈다.

코드

---

import sys

n = int(sys.stdin.readline())
board = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
dp = [[-1] * n for _ in range(n)]

for k in range(1, n):
    for x in range(n - k):
        y = x + k
        flag = 1000
        res = 0
        for i in range(x, y):
            if i > flag:
                break
            for j in range(i + 1, y + 1):
                if board[i][j]:
                    flag = min(flag, j)
                    sub_res = 1
                    if i + 1 < j - 1:
                        sub_res += dp[i + 1][j - 1]
                    if j + 1 < y:
                        sub_res += dp[j + 1][y]
                    res = max(res, sub_res)
        
        dp[x][y] = res

print(dp[0][-1])

TLE가 나올까봐 Bottom-Up 방식의 코드를 제출했는데, Top-Down 방식도 통과한다.

#include <iostream>
#include <algorithm>

using namespace std;

int n, temp;
int board[500][500], dp[500][500];

int f(int x, int y) {
    if (x > y) {
        return 0;
    }
    
    if (dp[x][y] != -1) {
        return dp[x][y];
    }

    int res = 0;
    int flag = 1000;
    for (int i = x; i < y; i++) {
        if (i > flag) {
            break;
        }
        for (int j = i + 1; j < y + 1; j++) {
            if (board[i][j]) {
                flag = min(flag, j);
                res = max(res, f(i + 1, j - 1) + f(j + 1, y) + 1);
            }
        }
    }

    dp[x][y] = res;
    return res;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n;

    for (int x = 0; x < n; x++) {
        for (int y = 0; y < n; y++) {
            cin >> temp;
            board[x][y] = temp;
            dp[x][y] = -1;
        }
    }

    cout << f(0, n - 1);

    return 0;
}

C++로 제출한 코드이다.

시간 비교

---

언어	방식	시간	메모리
PyPy3	재귀	2160ms	136048KB
PyPy3	for문	8684ms	130380KB
C++	재귀	468ms	3974KB
C++	for문	2060ms	3972KB
Python3	재귀	TLE	-

PyPy3와 메모리를 비교해보려 Python3도 제출해봤지만 역시나 TLE가 뜬다.

PyPy3와 C++ 둘 다 Bottom-Up 방식보다 Top-Down 방식이 훨씬 빠른 것을 알 수 있는데, 이는 전자가 발생하지 않을 부분 문제에 대해서도 계산을 해서 그런 것으로 추측된다.

완전 그래프일 때는 시간이 비슷할 것 같은데 더 이상의 깊은 생각은 생략한다.

아무튼 DP는 너무 어렵다.