[백준 #1533] 길의 개수 - JAVA [자바]

분류

분할 정복을 이용한 거듭제곱, 그래프 이론, 수학

 

문제 설명

세준이는 정문이를 데리러 공항으로 가기로 했다. 하지만, 방금 세준이는 정문이의 비행기가 연착된다는 전화를 받았다. 세준이는 정문이가 정확하게 몇 분 늦는지 알고 있고, 그 시간 동안 밖에서 드라이브를 하려고 한다. 정문이가 늦는 시간을 T라고 하자.

세준이는 자기가 지금 있는 위치에서부터, 공항까지 정확하게 T분만에 도착하는 경로의 개수를 구하고 싶다.

길의 정보는 인접행렬로 주어진다. A[i][j]가 0이라면 i에서 j로 가는 길이 없는 것이고, A[i][j] ≤ 5라면, 정확히 그 만큼의 시간이 걸리는 i에서 j로 가는 길이 있는 것이다.

 

입력

첫째 줄에 교차점의 개수 N이 주어진다. N은 10보다 작거나 같고, 시작점의 위치 S와 끝점의 위치 E, 그리고 정문이가 늦는 시간 T도 주어진다. S와 E는 N보다 작거나 같은 자연수이다. T는 1,000,000,000보다 작거나 같은 자연수이다. 둘째 줄부터 길의 정보가 주어진다.

 

출력

첫째 줄에 경로의 개수를 1,000,003로 나눈 나머지를 출력한다.

 

예제 입력

3 1 3 5
012
201
120

 

예제 출력

8

 

코드 - 길의 개수.java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    private static final int MOD = 1000003;
    private static int N, S, E;
    private static long T;
    private static long[][] A, ans;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] input = br.readLine().split(" ");
        N = Integer.parseInt(input[0]);
        S = Integer.parseInt(input[1]);
        E = Integer.parseInt(input[2]);
        T = Long.parseLong(input[3]);

        A = new long[5 * N + 1][5 * N + 1];
        ans = new long[5 * N + 1][5 * N + 1];
        for (int i = 1; i <= 5 * N; i++) ans[i][i] = 1;

        for (int i = 1; i <= N; i++) {
            String s = br.readLine();
            for (int j = 0; j < s.length(); j++) {
                if (s.charAt(j) - '0' >= 1) {
                    A[i * 5][(j + 1) * 5 - (s.charAt(j) - '0' - 1)] = 1;
                }
            }
            for (int j = 1; j <= 4; j++) {
                A[(i - 1) * 5 + j][(i - 1) * 5 + j + 1] = 1;
            }
        }

        mpow();

        System.out.println(ans[5 * S][5 * E]);
    }

    private static void mpow() {
        while (T > 0) {
            if (T % 2 == 1) {
                ans = multiply(ans, A);
            }
            T /= 2;
            A = multiply(A, A);
        }
    }

    private static long[][] multiply(long[][] a, long[][] b) {
        long[][] res = new long[5 * N + 1][5 * N + 1];
        for (int i = 1; i <= 5 * N; i++) {
            for (int j = 1; j <= 5 * N; j++) {
                for (int k = 1; k <= 5 * N; k++) {
                    res[i][j] += (a[i][k] * b[k][j]);
                    res[i][j] %= MOD;
                }
            }
        }
        return res;
    }
}

 

코드 분석하기

이 문제는 그래프 이론과 분할 정복 알고리즘을 활용하여 풀 수 있습니다. 주어진 시간 T 내에 시작점에서 도착점까지 이동하는 경로의 개수를 구하는 것이 목표입니다. 이 문제를 푸는 기본 아이디어는 인접 행렬을 이용한 그래프 표현과 행렬의 거듭제곱을 이용하여 T시간 안에 이동할 수 있는 경로의 개수를 구하는 것입니다.

1. 먼저, 주어진 그래프를 인접 행렬로 표현합니다. 인접 행렬 A[i][j]는 노드 i에서 노드 j로 이동하는데 걸리는 시간을 나타냅니다. 이때, 주어진 시간이 5보다 작거나 같으므로, 각 노드를 5개의 부노드로 나누어 각각을 1분 단위로 이동할 수 있는 경로로 간주합니다. 이렇게 하면, 각 경로는 정확히 1분의 시간을 소요하게 됩니다.
2. 그런 다음, 행렬의 거듭제곱을 통해 T분 안에 갈 수 있는 모든 경로의 개수를 계산합니다. 이는 분할 정복 알고리즘을 이용하여 효율적으로 계산할 수 있습니다. T가 짝수일 경우 A를 A^2로, 홀수일 경우 결과 행렬 ans에 A를 곱하고 A를 A^2로 업데이트합니다. 이를 T가 0이 될 때까지 반복합니다. 이 과정을 거치면, ans 행렬은 시작점에서 도착점까지 정확히 T분 만에 이동하는 경로의 개수를 나타내게 됩니다.
3. 마지막으로, ans[S][E]를 1,000,003으로 나눈 나머지를 출력하면 원하는 결과를 얻을 수 있습니다.

이런 방식으로 문제를 해결하면, 주어진 시간 T 내에 시작점에서 도착점까지 이동하는 모든 가능한 경로의 개수를 효과적으로 계산할 수 있습니다.

변수 선언:

private static final int MOD = 1000003;
private static int N, S, E;
private static long T;
private static long[][] A, ans;

위의 변수들은 모두 클래스 레벨에서 선언되었습니다. N, S, E, T는 문제에서 주어진 변수들이며, A와 ans는 길의 정보와 결과를 저장하는 2차원 배열(행렬)입니다. **MOD**는 나머지 연산에 사용되는 상수입니다.

입력 받기:

N = Integer.parseInt(input[0]);
S = Integer.parseInt(input[1]);
E = Integer.parseInt(input[2]);
T = Long.parseLong(input[3]);

위 코드는 사용자로부터 입력을 받아 각 변수에 저장하는 부분입니다. 이 때, **T**는 값이 매우 클 수 있기 때문에 long 타입으로 선언되었습니다.

행렬 초기화:

A = new long[5 * N + 1][5 * N + 1];
ans = new long[5 * N + 1][5 * N + 1];
for (int i = 1; i <= 5 * N; i++) ans[i][i] = 1;

A는 길의 정보를 저장하고, ans는 단위 행렬로 초기화됩니다. ans가 단위 행렬로 초기화되는 이유는 거듭제곱 연산을 위해 초기 곱셈의 항등원이 필요하기 때문입니다.

거듭제곱 연산:

private static void mpow() {
    while (T > 0) {
        if (T % 2 == 1) {
            ans = multiply(ans, A);
        }
        T /= 2;
        A = multiply(A, A);
    }
}

mpow 함수에서는 분할 정복을 이용하여 거듭제곱 연산을 수행합니다. 이는 효율적인 거듭제곱 계산을 위해 사용되는 알고리즘입니다.

행렬 곱셈:

private static long[][] multiply(long[][] a, long[][] b) {
    long[][] res = new long[5 * N + 1][5 * N + 1];
    for (int i = 1; i <= 5 * N; i++) {
        for (int j = 1; j <= 5 * N; j++) {
            for (int k = 1; k <= 5 * N; k++) {
                res[i][j] += (a[i][k] * b[k][j]);
                res[i][j] %= MOD;
            }
        }
    }
    return res;
}

multiply 함수는 두 행렬을 인자로 받아 곱한 결과를 반환합니다. 행렬의 곱셈은 각 원소의 합에 해당하는 곱셈을 수행하며, 결과는 MOD로 나눈 나머지로 저장됩니다. 이는 문제에서 요구하는 "경로의 개수를 1,000,003으로 나눈 나머지"를 출력하는 조건을 충족시키기 위함입니다.

결과 출력:

System.out.println(ans[5 * S][5 * E] % MOD);

마지막으로, 거듭제곱 연산이 끝난 후, ans 행렬의 S행 E열 값이 바로 시작점 S에서 도착점 E까지 정확히 T분 만에 도착하는 경로의 개수입니다. 이 값을 출력합니다. 이 값도 마찬가지로 MOD로 나눈 나머지를 출력합니다.

이 코드는 인접 행렬을 이용한 그래프 표현과 분할 정복을 통한 효율적인 거듭제곱 계산, 행렬 곱셈 등의 개념을 사용합니다. 이러한 방식은 그래프에서의 최단 경로 문제나 다이나믹 프로그래밍 문제 등에서 자주 사용됩니다.

 

 

백준에서 문제 풀어보기

 

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

1533번: 길의 개수