백준 - 1533 길의 개수 JAVA

🎲문제

---

 

주소: 백준 1533

세준이는 정문이를 데리러 공항으로 가기로 했다. 하지만, 방금 세준이는 정문이의 비행기가 연착된다는 전화를 받았다. 세준이는 정문이가 정확하게 몇 분 늦는지 알고 있고, 그 시간 동안 밖에서 드라이브를 하려고 한다. 정문이가 늦는 시간을 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보다 작거나 같은 자연수이다. 둘째 줄부터 길의 정보가 주어진다.

 

 

🧐풀이

---

 

풀이방법

T의 숫자가 너무 크기 때문에 O(V^2*T)의 DP로 풀으려고 한다면 시간 초과가 날 것이다. 만약 가중치가 1인 그래프라면 인접 행렬 그래프 방식으로 풀 수 있다. 가중치가 1인 인접 행렬 그래프를 n번 제곱하면 S에서 E로 가는 경로중 n개의 간선이 있는 경로의 수와 같기 때문이고, O(V^3 * logT)의 연산이라 T의 수를 현저히 줄일 수 있기 때문이다. 하지만 해당 문제에서는 가중치가 5이하이다.

이는 N의 개수가 적기 때문에 하나의 정점을 5개로 분할하여 계산하여도 계산 상 큰 문제가 없을 것이다.

이 때, N5 x N5의 매트릭스가 만들어질텐데 원래 정점이 아닌 분할된 정점들은 자신보다 1이 큰 정점으로 가중치가 1로 주어지므로, (i * 5 - 가중치)로 그래프를 그린다면 전체 행렬을 가중치가 1인 행렬로 만들 수 있다.

이후 행렬제곱을 구현하여 곱해주면 된다.

 

1. N과 S, E, T를 입력받고 값을 입력받을 배열(N*5사이즈)을 생성한다.

 

2. 다음줄의 string 값을 입력받고 사이즈만큼 하나씩 숫자를 잘라 해당 숫자가 0이 넘는지 체크하고 0이 넘는다면 [i*5][(j + 1) * 5 - 가중치 -1] 의 가중치를 둔다.

 

3. 분할된 정점들은 자신보다 1 큰 수로 향하는 방향으로 가중치를 둔다.

import java.util.Scanner;

public class Main{

    static Scanner sc = new Scanner(System.in);
    static long[][] array;
    static long[][] ans;
    static int N, S, E, T;

    static final int MOD = 1000003;
    public static void main(String[] args) {

        N = sc.nextInt();
        S = sc.nextInt();
        E = sc.nextInt();
        T = sc.nextInt();
        array = new long[(N * 5) + 1][(N * 5) + 1];
        sc.nextLine();

        for(int i = 1; i <= N; i++) {
            String s = sc.nextLine();
            for (int j = 0; j < s.length(); j++){
                if (s.charAt(j) != '0') {
                    array[i * 5][(j + 1) * 5 - (s.charAt(j) - '0' - 1)] = 1;
                }
            }

            for(int j = 1; j < 5; j++)
                array[(i - 1) * 5 + j][(i - 1) * 5 + j + 1] = 1;

        }

        System.out.println(powProcession(array,T)[5*S][5*E]);
    }

 

 

4.  array 배열을 T만큼 곱할 결과 값을 담을 result 배열을 설정한다.

 

5. T가 홀수이면 result에 array를 곱하고 짝수라면 array를 제곱한다. T를 2로 나누고 0이 될때까지 반복한다. 마지막에는 무조건 T가 1이므로 result에 전체 제곱한 값이 담긴다.

    public static long[][] powProcession(long[][] a, int n){

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

        while(n != 0){

            if(n % 2 == 1)
                result = squareProcession(result, a);

            n /= 2;
            a = squareProcession(a,a);

        }

        return result;
    }

 

 

 

6. 행렬 두 개를 입력받고 서로 곱해주는 함수를 작성한다. 곱해주면서 값이 매우 커지는 경우가 있으므로 초기에 설정한 MOD값으로 계속 나눠준다.

    public static long[][] squareProcession(long[][] a, long[][] b) {

        long[][] result = new long[N * 5 + 1][N * 5 + 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++) {
                    result[i][j] += (a[i][k] * b[k][j]);
                    result[i][j] %= MOD;
                }
            }
        }
        return result;
    }

 

 

🧠전체 코드

---

import java.util.Scanner;

public class Main{

    static Scanner sc = new Scanner(System.in);
    static long[][] array;
    static long[][] ans;
    static int N, S, E, T;

    static final int MOD = 1000003;
    public static void main(String[] args) {

        N = sc.nextInt();
        S = sc.nextInt();
        E = sc.nextInt();
        T = sc.nextInt();
        array = new long[(N * 5) + 1][(N * 5) + 1];
        sc.nextLine();

        for(int i = 1; i <= N; i++) {
            String s = sc.nextLine();
            for (int j = 0; j < s.length(); j++){
                if (s.charAt(j) != '0') {
                    array[i * 5][(j + 1) * 5 - (s.charAt(j) - '0' - 1)] = 1;
                }
            }

            for(int j = 1; j < 5; j++)
                array[(i - 1) * 5 + j][(i - 1) * 5 + j + 1] = 1;

        }

        System.out.println(powProcession(array,T)[5*S][5*E]);
    }

    public static long[][] squareProcession(long[][] a, long[][] b) {

        long[][] result = new long[N * 5 + 1][N * 5 + 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++) {
                    result[i][j] += (a[i][k] * b[k][j]);
                    result[i][j] %= MOD;
                }
            }
        }
        return result;
    }

    public static long[][] powProcession(long[][] a, int n){

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

        while(n != 0){

            if(n % 2 == 1)
                result = squareProcession(result, a);

            n /= 2;
            a = squareProcession(a,a);

        }

        return result;
    }