[SWEA/D6] SWEA 1260 [S/W 문제해결 응용] 7일차 - 화학물질2(Java)

문제 출처

SW Expert Academy

 

알고리즘 분류

• 다이나믹 프로그래밍
• 그래프 탐색
• 백트래킹

 

풀이

먼저 창고에 존재하는 모든 화학 물질 용기를 조사한다. 이는 BFS로 처리할 수 있으며, BFS를 수행하면 직사각형이 나올 텐데 이 직사각형의 높이와 너비를 기록해둔다.

창고를 조사한 후에는 최대 20개의 직사각형 형태의 화학 물질 용기가 나올 것이며, 이를 HXW 크기의 행렬이라고 가정한다.

이제부터는 모든 화학 물질 용기를 섞는 최소의 횟수를 구해야 하며, 이 때 연쇄 행렬 최소 곱셈 알고리즘(이하 MCM, Multiple Chain Matrix Algorithm)이라는 걸 사용한다.

그러기 위해서는, 먼저 모든 행렬을 곱할 수 있는 순서로 정렬해야 하며, 이 때 백트래킹으로 가능한 순서를 정한다.

행렬의 순서를 정한 후에 MCM을 사용하게 된다.

먼저 행렬 A부터 행렬 B까지 곱하는 최소의 횟수를 기록하는 DP[A][B]라는 2차원 배열을 선언한다. 행렬은 최대 20개까지 등장한다.

 

 

이렇게 정의된다고 하며 이를 바탕으로 점화식을 세우면 된다.

우리는 여기서 DP[1][N], 즉 첫 번째 행렬부터 N번째 행렬까지의 곱하는 최소의 횟수를 구한다.

 

출처

https://doooooooong.tistory.com/10

[DP] Multiply Chain Matrix Algorithm

 

코드

import java.io.*;
import java.util.*;
 
public class Solution {
     
    private static class Position {
         
        int Y, X;
 
        public Position(int y, int x) {
            super();
            Y = y;
            X = x;
        }
 
        @Override
        public String toString() {
            return "Position [Y=" + Y + ", X=" + X + "]";
        }
         
    }
     
    private static class Matrix {
         
        int H, W;
 
        public Matrix(int h, int w) {
            super();
            H = h;
            W = w;
        }
 
        @Override
        public String toString() {
            return "Matrix [H=" + H + ", W=" + W + "]";
        }
    }
     
    private static int N;
    private static List<Matrix> matrixes;
    private static int[][] map = new int[101][101];
    private static boolean[][] visited = new boolean[101][101];
    private static boolean[] matrixVisited = new boolean[21];
    private static int[] moveY = { -1,0,1,0 };
    private static int[] moveX = { 0,-1,0,1 };
    private static int Answer;
    private static StringBuilder sb = new StringBuilder();
     
    private static void init() {
        matrixes = new ArrayList<Matrix>();
        for (int i = 0; i < 101; i++) {
            for (int j = 0; j < 101; j++) {
                map[i][j] = 0;
                visited[i][j] = false;
            }
        }
        for (int i = 0; i < 21; i++) {
            matrixVisited[i] = false; 
        }
        Answer = Integer.MAX_VALUE;
    }
     
    private static void bfs(int Y, int X) {
        Queue<Position> queue = new LinkedList<>();
        queue.add(new Position(Y, X));
        visited[Y][X] = true;
        int lowH = Y;
        int highH = 0;
        int lowW = X;
        int highW = 0;
         
        while (!queue.isEmpty()) {
            Position now = queue.poll();
            int nowY = now.Y;
            int nowX = now.X;
             
            lowH = Math.min(lowH, nowY);
            highH = Math.max(highH, nowY);
            lowW = Math.min(lowW, nowX);
            highW = Math.max(highW, nowX);
             
            for (int i = 0; i < 4; i++) {
                int nextY = nowY + moveY[i];
                int nextX = nowX + moveX[i];
                if ((nextY >= 1) && (nextY <= N) && (nextX >= 1) && (nextX <= N) && !visited[nextY][nextX] && (map[nextY][nextX] > 0)) {
                    queue.add(new Position(nextY, nextX));
                    visited[nextY][nextX] = true;
                }
            }
        }
         
        matrixes.add(new Matrix(highH - lowH + 1, highW - lowW + 1));
    }
     
    private static void dfs(int Depth, List<Matrix> list) {
        if (Depth == matrixes.size()) {
            int[][] dp = new int[21][21];
             
            for (int i = 1; i < list.size(); i++) {
                for (int s = 1; s <= list.size() - i; s++) {
                    int e = s + i;
                    dp[s][e] = Integer.MAX_VALUE;
                    for (int m = s; m < e; m++) {
                        dp[s][e] = Math.min(dp[s][e], dp[s][m] + dp[m + 1][e] + (list.get(s - 1).H * list.get(m - 1).W * list.get(e - 1).W));
                    }
                }
            }
             
            Answer = dp[1][list.size()];
             
            return;
        }
         
        for (int i = 0; i < matrixes.size(); i++) {
            if (matrixVisited[i]) continue;
            if (list.get(Depth - 1).W != matrixes.get(i).H) continue;
            matrixVisited[i] = true;
            List<Matrix> newList = list;
            newList.add(matrixes.get(i));
            dfs(Depth + 1, newList);
            matrixVisited[i] = false; 
        }
    }
 
    private static void settings() {
        // 1. 행렬들 구하기
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (!visited[i][j] && (map[i][j] > 0)) {
                    bfs(i, j);
                }
            }
        }
         
        // 2. 연쇄행렬 최소곱셈
        for (int i = 0; i < matrixes.size(); i++) {
            if (matrixVisited[i]) continue;
            matrixVisited[i] = true;
            List<Matrix> newList = new ArrayList<>();
            newList.add(matrixes.get(i));
            dfs(1, newList);
            matrixVisited[i] = false; 
        }
    }
     
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
          
        int Total = Integer.parseInt(br.readLine());
        for (int test_case = 1; test_case <= Total; test_case++) {
            init();
             
            sb.append("#" + test_case + " ");
 
            N = Integer.parseInt(br.readLine());
            for (int i = 1; i <= N; i++) {
                String[] inputs = br.readLine().split(" ");
                for (int j = 1; j <= N; j++) {
                    map[i][j] = Integer.parseInt(inputs[j - 1]); 
                }
            }
             
            settings();
             
            sb.append(Answer + "\n");
        }
          
        bw.write(sb.toString());
        bw.close();
        br.close();
    }
 
}