swea 1260 화학물질2 Java (연쇄행렬 최소곱셈)

문제 출처 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18OR16IuUCFAZN 

SW Expert Academy

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.

유엔 화학 무기 조사단이 대량 살상 화학 무기를 만들기 위해 화학 물질들이 저장된 창고를 조사하게 되었다.

창고에는 화학 물질 용기 n2개가 n x n으로 배열되어 있었다.

유엔 조사단은 각 용기를 조사하여 2차원 배열에 그 정보를 저장하였다.

빈 용기에 해당하는 원소는 ‘0’으로 저장하고, 화학 물질이 들어 있는 용기에 해당하는 용기는 화학 물질의 종류에 따라 ‘1’에서 ‘9’사이의 정수를 저장하였다.

다음 그림은 창고의 화학 물질 현황을 9x9 배열에 저장한 예를 보여준다.
 

유엔 조사단은 화학 물질이 담긴 용기들로부터 2가지 사항을 발견하였다.

1. 화학 물질이 담긴 용기들이 사각형을 이루고 있다. 또한, 사각형 내부에는 빈 용기가 없다.

예를 들어, 위의 그림에는 3개의 화학 물질이 담긴 용기들로 이루어진 사각형 A, B, C가 있다.

2. 2개의 화학 물질이 담긴 용기들로 이루어진 사각형들 사이에는 빈 용기들이 있다.

예를 들어, 위의 그림에서 A와 B사이와 B와 C사이를 보면, 빈 용기를 나타내는 ‘0’ 원소들이 2개의 사각형 사이에 있는 것을 알 수 있다.

단, A와 C의 경우와 같이 대각선 상으로는 빈 용기가 없을 수도 있다.

또한 유엔 조사단은 화학 물질이 담긴 용기들로 이루어진 사각형들 사이에 특정한 관계가 있는 것을 추후 조사를 통해서 알아내었다.

그 관계는 바로 화학 물질이 든 용기들로 이루어진 각 사각형을 행렬이라고 여겨, 행렬 간의 곱셈을 수행하는 방식으로 화학 물질을 섞는 것이다.

즉, 2개의 행렬 원소 간 곱셈은 2개의 행렬 원소에 대응되는 화학 물질을 섞는 것이다.

단, 섞은 물질들을 합치는 데는 시간이 걸리지 않는다고 가정한다.

예를 들어, 그림에서 3개의 행렬 A, B, C의 차원이 각각 3x4, 2x3, 4x5이므로, 행렬간 곱셈을 수행하기 위해 반드시 BxAxC로 곱셈이 수행되어야 한다.

그러나 어떤 행렬들을 먼저 곱하는 것에 따라 행렬 원소간의 곱셈 수가 달라질 수 있다.

예를 들어, 위 그림에서 3개의 행렬 (A(3x4), B(2x3), C(4x5))의 곱셈을 살펴보면, (B*A)*C, 즉, B*A를 먼저 수행하고 그 결과 행렬을 C 와 곱하면, 64번의 원소간 곱셈이 수행된다.

그러나 B*(A*C)의 경우는 90번의 곱셈이 필요하다.

유엔 조사단의 시간을 절약하기 위해, 창고의 용기들에 대한 2차원 배열에서 행렬(화학 물질이 든 용기들로 이루어진 사각형)들을 찾아내고,

찾아낸 행렬들 간의 곱셈에 필요한 최소 원소간의 곱셈 수 (2개의 화학 물질이 든 용기를 섞는 작업의 수)를 찾는 프로그램을 작성하시오.

[제약 사항]

n은 100 이하이다.

부분 행렬의 열의 개수는 서로 다르며 행렬의 행의 개수도 서로 다르다.

예를 들어, 3개의 부분행렬 행렬 (A(3x4), B(2x3), C(4x5))이 추출되었다면, 각 부분 행렬의 행의 수는 3, 2, 4로 서로 다르다.

마찬가지로 각 부분 행렬의 열의 수도 4, 3, 5로 서로 다르다.

그래서 각 테스트 케이스에서 추출된 행렬들 사이의 곱셈에는 반드시 1개의 수행 가능한 행렬 곱셈 순서만 존재한다.

행렬들 사이의 차원이 맞지 않아 곱셈을 수행할 수 없는 테스트 케이스는 주어지지 않는다.

테스트 케이스는 여러 개의 그룹으로 구성되며 아래와 같다.
그룹 1. n <= 10 이고 sub matrix의 개수 5개 이하
그룹 2. n <= 40 이고 5 < sub matrix <= 10
그룹 3. 40 < n <=80 이고 5 < sub matrix <= 10
그룹 4. 40 < n <=80 이고 10 < sub matrix <= 15
그룹 5. 80 < n<=100 이고 15 < sub matrix <= 20

[입력]

맨 첫 줄에는 테스트 케이스의 개수가 주어진다.

그리고 테스트 케이스가 각 라인에 주어진다.

각 테스트 케이스는 (n+1) 줄로 구성되며, 첫 줄에는 양의 정수인 n이 주어지고, 다음 n줄에는 n x n 행렬이 (각 행이 한 줄에) 주어진다.

[출력]

각 테스트 케이스 각각에 대한 답을 출력한다.

각 줄은 ‘#x’로 시작하고 공백을 하나 둔 다음, 각 테스트 케이스에 주어진 행렬에서 추출된 부분 행렬들을 곱하는데 필요한 최소의 원소 간의 곱셈 수를 출력한다.

풀이

연쇄행렬 최소 곱셈이란 알고리즘을 처음 접했다.

dp를 이용한 알고리즘으로, 말 그대로 연속적인 행렬을 곱할 때 원소 간의 곱셈 수를 최소로 하는 경우를 찾는 알고리즘이다.

알고리즘에 대한 설명을 듣고 나서야 풀 수 있었는데, 이 복잡한 풀이가 그래도 정리된 알고리즘이 있기 때문에 이 패턴을 익힌다면 다음에  같은 문제가 나와도 어렵지 않게 풀 수 있을 것이다.

 

우선 문제에서 요구하는 것은, 주어진 그래프에서 부분 행렬을 찾아 행렬의 행과 열 사이즈를 저장, 이 부분 행렬들을 연속적으로 곱해서 최종적으로 하나의 행렬을 만드는 것이다.

 

기억 저편에서 행렬의 곱셈에 대한 규칙을 끄집어내려 했으나 역시나 기억이 나지 않았고, 구글링을 통해 행렬 곱셈에 대한 규칙을 파악했다.

두 행렬을 곱하는 조건은 r1Xc1 * r2Xc2 에서 c1 ==r2를 만족해야 하고, 행렬 곱셈의 결과는 r1Xc2 사이즈의 행렬이 나온다.

이 문제에선 모든 부분 행렬이 이 조건을 위배하여 최종적으로 곱해진 하나의 행렬을 만들지 못하는 케이스는 없다고 한다.

 

이제 알고리즘에 관한 얘기를 하자면, dp와 위의 행렬 곱셈 규칙을 이용한 알고리즘이라 할 수 있다.

준비물로는

dp[][]

subMatrix[][]

d[]

정도가 필요한데,

dp[i][j] = i번 째 행렬에서 j번째 행렬까지 최소 연산 횟수(점화식을 이용해 구한다)

subMatrix[n][2] = 보통은 그냥 matrix인데 이 문제에선 전체 행렬(그래프)가 주어지고 거기서 행렬을 뽑아내기 때문에 subMatrix라

                                명명했다. 각 행렬의 row,column사이즈를 저장한다.

d[] = d배열이 이해하기 힘들었는데, 풀이의 편의성을 위한 유틸 배열이다. 즉 d배열 없이 위의 matrix배열로도 풀 수 있다.

 

d배열에 관해선 아래서 설명하기로 하고 일단 dp를 이용한 알고리즘이니 당연히 점화식이 필요할 것이다.

점화식은 다음과 같다.

dp[i][j] = min(dp[i][k] + m[k+1][j] + d[i-1]*d[k]*d[j])

 

어우.. 한 문제 푼 걸론 이 알고리즘을 설명할 자신이 없다.

이해를 돕기 위해 참고한 블로그를 첨부한다.

https://source-sc.tistory.com/24

https://pupuduck.tistory.com/14

 

d배열에 관해 설명하는 것도, 알고리즘에 관해 설명하는 것도 표를 그려 설명해야 한다.

하지만 내 맥북엔 아직 power point가 없다.

고로 추후에 완벽히 이해해서 표를 그려가며 포스팅을 완성하겠다...!!

 

5X2, 2X3, 3X4, 4X6, 6X7, 7X8      6개의 행렬이 있다고 하자.

 

 

 

코드

import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
class Solution {
     
    static char[][] graph;
    static int[][] subMatrix = new int[21][2];
    static int[][] dp = new int[21][21];
    static int[] d = new int[21];
    static int mCnt =0;
    static int n;
     
    static void getSubMatrix(int i, int j) {
        int r=0,c=0;
        for(; i+r<n && graph[i+r][j]!='0'; r++) {
            for(c=0; j+c<n && graph[i+r][j+c]!='0'; c++) {
                graph[i+r][j+c] ='0';
            }
        }
        subMatrix[mCnt][0] = r;
        subMatrix[mCnt][1] = c;
        mCnt++;
    }
     
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int T = Integer.parseInt(br.readLine());
        for (int t = 1; t <= T; t++) {
            // input
            mCnt=0;
            n =Integer.parseInt(br.readLine());
            graph = new char[n][n];
            for(int i=0; i<n; i++) {
                StringTokenizer tk = new StringTokenizer(br.readLine());
                for(int j=0; j<n ;j++) {
                    graph[i][j] = tk.nextToken().charAt(0);
                }
            }
            //solve
            //getsubMatrix
            for(int i=0; i<n; i++) {
                for(int j=0; j<n; j++) {
                    if(graph[i][j]!='0') {
                        getSubMatrix(i,j);
                    }
                }
            }
 
            int start;
            for(start=0; start< mCnt; start++) {
                 
                 
                int j;
                for(j=0; j< mCnt;j++) {
                    if(subMatrix[start][0] == subMatrix[j][1]) break;
                }
                //수행 가능한 행렬 곱셈 순서가 없는 경우
                if(j==mCnt) break;
                 
            }
            //연쇄 행렬로부터 d값 추출
            //d는 매트릭스를 곱셈 순서에 맞게 행렬 곱셉에 필요한 가운데 값을 저장한다.
            //ex) aXb * bXc 에서 b를 저장한다. 단, 시작 점인 d[0]은 시작 행렬의 aXb에서 a를 저장 
            d[0] = subMatrix[start][0];
             
            for(int i=0; i<mCnt; i++) {
                for(int j=0; j< mCnt; j++) {
                    if(subMatrix[j][0] == d[i]) {
                        d[i+1] = subMatrix[j][1];
                        break;
                    }
                }
            }
             
            //dp 초기화
            for(int i=0; i<= mCnt;i++) {
                for(int j=0; j<= mCnt; j++) {
                    if(i==j) {
                        dp[i][j] = 0;
                    }
                    else {
                        dp[i][j] = Integer.MAX_VALUE;
                    }
                }
            }
 
            //점화식으로 dp 채워넣기
            //dp[i][j] ==  i에서 j까지 연결했을 때의 최소 행렬 곱셈
            for(int x=1; x<= mCnt; x++) {
                for(int i=1; i<= mCnt-x; i++) {
                    int j= i+x;
                    int temp;
                    for(int k=i; k<=j-1; k++) {
                        temp = dp[i][k] + dp[k+1][j] + d[i-1]*d[k]*d[j];
                        if(temp < dp[i][j]) {
                            dp[i][j] = temp;
                        }
                    }
                }
            }
            // output   
             bw.write("#"+ t + " " +dp[1][mCnt] +"\n");
        }
        bw.close();
    }
}