분할 정복(Divide & Conquer)

분할 정복?

백준 12849번 : 본대 산책 백준 12850번 : 본대 산책2

발단은 위 두 문제이다.

첫 번째 문제를 dp로 무사히 해결했는데, 이어지는 문제가 있어서 확인했더니
이번엔 입력값이 10억까지 늘어났다.

기존 코드를 그대로 넣어봤더니 역시나 매우매우매우 부족했다.

해결해나가는 과정에서 분할정복이라는 기법을 알게됐는데, 문제를 부분 문제로 나누어 재귀적으로 해결한다고 한다.

일반적인 재귀함수와 무엇이 다른가 봤더니
일반적인 재귀호출은 하나의 조각과 나머지덩어리로 나누는데에 반해,
분할정복은 두개의 비슷한 덩어리로 나누는 차이가 있다고 한다.

이번 문제를 해결하는데에 있어서 이를 조금 응용해서 문제를 해결해봤다.

문제에서의 활용

그래프를 나타낸 행렬을 n번 곱하면 n번에 걸쳐 이동하는 횟수를 나타내는 행렬을 만들 수 있다는 점을 활용했다.

3차원 long long배열인 graph[31][9][9]를 선언해줬다.

그 후, graph[0]만을 초기화해줬는데, 8개의 건물에 각각 번호를 부여하고
두 건물이 만나는 지점은 1, 그렇지 않은 곳은 0으로 초기화해줬다.
예를 들어 2번건물과 3번건물은 이어져있으므로 graph[0][2][3]과 graph[0][3][2]는 1일 것이다.

graph[a]는 2의 a승만큼 초기값을 곱한 값을 저장한다. 예를 들어 graph[5]는 graph[0]을 2의 5승, 즉 32번 곱한 9*9 행렬을 나타낸다.

이를 활용하여, 큰 숫자를 여러개의 2의 거듭제곱의 합(부분문제)으로 나누어 해결하고자 했다.

    for (int i = 1; i <= 30; i++)
    {
        for (int j = 1; j <= 8; j++)
            for (int k = 1; k <= 8; k++)
            {
                temp = 0;
                for (int l = 1; l <= 8; l++)
                {
                    temp += graph[i - 1][j][l] * graph[i - 1][l][k];
                    temp %= 1000000007;
                }
                graph[i][j][k] = temp;
            }
    }

graph[1]은 graph[0]을 두번 곱하고, graph[2]는 graph[1]을 두번 곱하는 방식으로
graph[30]까지 2만번이내의 계산으로 충분히 저장할 수 있다.

    long long temp_arr[9][9];
    long long res[9][9];

    for (int i = 1; i <= 8; i++)
    {
        for (int j = 1; j <= 8; j++)
            res[i][j] = 0;
        res[i][i] = 1;
    }
    for (int i = 0; i <= 30; i++)
    {
        if ((time & ((long long)1 << i)) > 0)
        {
            for (int j = 1; j <= 8; j++)
                for (int k = 1; k <= 8; k++)
                {
                    temp = 0;
                    for (int l = 1; l <= 8; l++)
                    {
                        temp += res[j][l] * graph[i][l][k];
                        temp %= 1000000007;
                    }
                    temp_arr[j][k] = temp;
                }
            for (int j = 1; j <= 8; j++)
                for (int k = 1; k <= 8; k++)
                    res[j][k] = temp_arr[j][k];
        }
    }

최종 행렬을 나타내는 res행렬은 단위행렬로 초기화해주었다.

그 뒤 i = 0 부터 30까지 지나가며, (time & (1 << i)) > 0인지 검사한다.
즉 time을 2의 거듭제곱의 합으로 나타내는 과정이다.

조건문내에서는 res와 graph[i]의 곱을 다시 res에 저장한다.

예를 들어 time이 19라면 19 = 1 + 2 + 16이므로 i = 0일 때, i = 1일 때, i = 4일 때 총 3번 조건문에 들어가게 된다.

즉 res는 graph[0], graph[1], graph[4]를 곱한 값을 갖게 되므로
res는 초기행렬을 19번곱한 행렬을 갖게된다. 이러한 res행렬의 res[a][b]는 a에서 출발하여 19번 이동하여 b에 도착하는 경우의 수를 나타낸다.

우리가 찾고자 하는 답은 1번건물에서 출발하여 1번건물로 도착하는 경우의 수 이므로
res[1][1]이 된다.

분할정복을 통하여 기존의 해결방법이었던 dp에 비해 굉장히 효율적으로 해결할 수 있었다.

graph배열의 크기를 늘린다면 제시된 입력값의 최댓값인 1,000,000,000을 넘어서 훨씬 큰 수여도
문제없이 제한시간 내에 해결될 수 있을 것이다.