[알고리즘 문제 풀기] 본대 산책2(12850)

1. 문제 풀이 아이디어

• 경로를 인접 행렬로 만든 후, n번 거듭 제곱하여 0번 정점에서 0번 정점으로 돌아오는 경로의 수를 구해 문제를 해결한다.

2. 나의 정답 코드

using (StreamReader sr = new StreamReader(Console.OpenStandardInput()))
    using (StreamWriter sw = new StreamWriter(Console.OpenStandardOutput()))
{
    int n = int.Parse(sr.ReadLine());
    long[,] result = Solve(n);
    sw.WriteLine(result[0, 0]);
}

long[,] Solve(int n)
{
    n--;
    long[,] map = { {0,1,1,0,0,0,0,0},
                    {1,0,1,1,0,0,0,0},
                    {1,1,0,1,1,0,0,0},
                    {0,1,1,0,1,1,0,0},
                    {0,0,1,1,0,1,1,0},
                    {0,0,0,1,1,0,0,1},
                    {0,0,0,0,1,0,0,1},
                    {0,0,0,0,0,1,1,0} };
    long[,] result = map;
    long[,] mul = map;
    int count = 0;
    while (n > 0)
    {
        if ((n & 1) == 1) result = Mul(result, mul);
        mul = Mul(mul, mul);
        n >>= 1;
        count++;
    }
    return result;
}

long[,] Mul(long[,] a, long[,] b)
{
    long[,] result = new long[a.GetLength(0), b.GetLength(1)];
    for (int i = 0; i < result.GetLength(0); i++)
    {
        for (int j = 0; j < result.GetLength(1); j++)
        {
            for (int k = 0; k < a.GetLength(1); k++)
            {
                result[i, j] += a[i, k] * b[k, j];
                result[i, j] %= 1000000007;
            }
        }
    }
    return result;
}

3. 정리

• map 배열에 8개의 지도의 정보를 저장한다

• n 번 이동하는 경로 수를 구해야 하므로 인접 행렬을 거듭 제곱하여 전체 경로 수를 계산한다

• 빠른 제곱을 위해 비트 연산을 활용하여 행렬을 곱한다.

• 다시 돌아오는 최종 결과인 result[0, 0]을 출력한여 문제를 해결한다.