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

문제 URL :https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18OR16IuUCFAZN&categoryId=AV18OR16IuUCFAZN&categoryType=CODE&problemTitle=%EC%9D%91%EC%9A%A9&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

SW Expert Academy

 

문제 접근법 : 

이전글 swea 1258 행렬찾기의 연장선문제입니다.

 

그치만 이문제를 풀기위해선 행렬찾기와 금속막대 아래링크:

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18NaZqIt8CFAZN&categoryId=AV18NaZqIt8CFAZN&categoryType=CODE&problemTitle=%EC%9D%91%EC%9A%A9&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

SW Expert Academy

 

이문제를 풀고

 

그다음 백준의 https://www.acmicpc.net/problem/11049

행렬곱셈순서를 푸시길 권장드립니다.

 

이 3개의 문제를 정확하게 섞은문제라

 

해당사각형 + 그리고 행렬곱셈을 할수있게 만들도록 한후 + dp를 이용해서 풀어야하는 문제입니다.

 

소스코드 : 

 

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Solution {
    public static int dy[]=new int[]{-1,0,1,0};
    public static int dx[]=new int[]{0,1,0,-1};
    public static int n;
    public static int board[][];
    public static int minx,miny,maxx,maxy;
    public static int dp[][];
    public static List<int[]>matrix;
    public static boolean check[];
    public static void main(String[] args) throws FileNotFoundException {
        //System.setIn(new FileInputStream("input.txt"));
        Scanner sc= new Scanner(System.in);
        int Test = sc.nextInt();
        for(int test=1;test<=Test;test++){
            n = sc.nextInt();
            board= new int[n][n];
            for(int i =0;i<n;i++){
                for(int j=0;j<n;j++){
                    board[i][j]=sc.nextInt();
                }
            }
            List<int[]> res = new ArrayList<>();
            for(int i =0;i<n;i++){
                for(int j=0;j<n;j++){
                    if(board[i][j]>0){
                        minx=miny = (int)1e9;
                        maxx=maxy = 0;
                        dfs(i,j);
                        res.add(new int[]{maxy-miny+1,maxx-minx+1});
                    }
                }
            }
            int N  = res.size();
            check = new boolean[N];
            List<int[]>list = new ArrayList<>();
            matrix = new ArrayList<>();
            dfs2(res,list,0);

            dp = new int[N][N];
            for (int i=0;i<N;i++) Arrays.fill(dp[i],(int)1e9);
            System.out.println("#"+test+" "+cal(0,N-1,matrix)+" ");
        }
    }
    public static boolean isrange(int y,int x){
        return 0<=y&&y<n&&0<=x&&x<n;
    }
    public static void dfs(int y,int x){
        if(!isrange(y,x))
            return;
        if(board[y][x]==0)return;
        board[y][x]=0;
        maxx=Math.max(maxx,x);
        maxy=Math.max(maxy,y);
        minx=Math.min(minx,x);
        miny=Math.min(miny,y);
        for(int i =0;i<4;i++){
            int ny=y+dy[i];
            int nx=x+dx[i];
            dfs(ny,nx);
        }
    }
    public static void dfs2(List<int[]> res,List<int[]> list,int h){
        if(h>=res.size()){
            if(matrix.size()==0) {
                for (int i = 0; i < list.size(); i++) {
                    matrix.add(Arrays.copyOf(list.get(i), list.get(i).length));
                }
            }
            return;
        }
        if(h==0){
            for(int i =0;i<res.size();i++){
                check[i]=true;
                list.add(res.get(i));
                dfs2(res,list,h+1);
                list.remove(list.size()-1);
                check[i]=false;
            }
            return;
        }

        int mat[] = list.get(list.size()-1);
        for(int i =0;i<res.size();i++){
            if(check[i]==false&&mat[1]==res.get(i)[0]){
                check[i]=true;
                list.add(res.get(i));
                dfs2(res,list,h+1);
                list.remove(list.size()-1);
                check[i]=false;
            }
        }
    }
    public static int cal(int l,int r, List<int[]> list){
        if(l>r)return (int)1e9;
        if(l==r)return 0;
        int left[] = list.get(l);
        int right[] = list.get(r);
        if(l+1==r)return left[0]*left[1]*right[1];
        if(dp[l][r]!=(int)1e9)return dp[l][r];
        for(int i=l;i<=r;i++) {
            dp[l][r] = Math.min(dp[l][r], cal(l, i, list) + cal(i + 1, r, list) + left[0] * list.get(i)[1] * right[1]);
        }
        return dp[l][r];
    }

}

 

 

궁금한점 혹은 모르는점 어떤질문이든 댓글은 언제나 환영입니다.