[백준](Java) 14502 - 연구소

문제 링크

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

문제 풀이

너무 반복을 많이 돌리나 싶어서 생각만 했던 방법인데, 다른 방법이 떠오르지않아 무작정 구현해보았는데 한번에 성공했다. 시간 복잡도에 대해서 공부를 더 해야 할거 같은 생각이 들었다.

연구소에 격벽을 3개 세워야 하는데 어디다가 세워야 할지를 한번에 딱 알 수 없으므로 모든 경우의 수에 대해서 격벽을 세우고 bfs를 통해서 바이러스가 증식되는지 확인하는 logic으로 접근했다.

벽이 3개니깐 크게는 삼중 for문을 사영했다.
i, j , k 를 사용하는 for문이며 i는 0부터, j는 i보다는 1큰값, k는 j보다 1큰값을 시작점으로 잡았으며, 가로와 세로를 곱한 크기만큼 반복을 돌도록 설정했다.
일직선이 아니라 2차원 배열의 형태이므로 몫,나머지를 이용해서 좌표를 설정할 수 있을것이라고 생각했다.
map[i/m][i%m]

map[i/m][i%m]가 0인 경우에만 격벽을 세울 수 있으므로 아닌경우는 continue를 처리했다.
i,j,k에 격벽을 다 세우면 그 상태를 똑같이 가지고 있는 dummy_map이라는 배열을 만들어서 dummy_map을 사용하여 bfs를 돌렸다.

여기서 2차원 배열은 직접 값을 대입하는 방법으로만 deepCopy가 되므로 메서드르 만들어서 해결했다.

    public static int [][] deepCopy(int [][] dummy_map){
        for(int e1=0; e1<n; e1++ ){
            for(int e2=0; e2<m; e2++){
                dummy_map[e1][e2]=map[e1][e2];
            }
        }
        return dummy_map;
    }

또한 chk도 격벽 상태에 대한 bfs가 종료될때마다 초기화 해주었다.

    public static void resetChk(){
        for(int l=0; l<n; l++){
            Arrays.fill(chk[l],false);
        }
    }

격벽에 대한 bfs가 종료될때마다 해당 dummy_map의 0의 개수를 체크하고 최댓값을 갱신한다.

    public static void calc(int [][] dummy_map){
        int zero_cnt=0;
        for(int i=0; i<n; i++){
            for(int j=0; j<m;j++){
                if(dummy_map[i][j]==0){
                    zero_cnt++;
                }
            }
        }
        answer = Math.max(answer,zero_cnt);
    }

해당 격벽에 대한 bfs가 전부 끝나면 그 격벽은 다시 0으로 바꾸고 다음 격벽을 세운다.

코드

import java.util.*;

public class Main {

    static int n;
    static int m;
    static boolean[][] chk;
    static int [][] map;
    static int[] diry = {-1, 0, 1, 0};
    static int[] dirx = {0, 1, 0, -1};

    static int answer = 0;


    static class Node {
        int y;
        int x;

        public Node(int y, int x) {
            this.y = y;
            this.x = x;
        }
    }

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        map = new int[n][m];
        chk = new boolean[n][m];
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                map[i][j] = sc.nextInt();
            }
        }

        for (int i = 0; i < n * m; i++) {
            if(map[i/m][i%m]!=0){
                continue;
            }
            map[i/m][i%m]=1;
            for (int j = i + 1; j < n * m; j++) {
                if(map[j/m][j%m]!=0){
                    continue;
                }
                map[j/m][j%m]=1;
                for (int k = j + 1; k < n * m; k++) {
                    if(map[k/m][k%m]!=0){
                        continue;
                    }
                    map[k/m][k%m]=1;

                    int [][] dummy_map = new int[n][m];
                    dummy_map = deepCopy(dummy_map);
                    resetChk();

                    for(int p=0; p<n; p++){
                        for(int q=0;  q<m; q++){
                            if(dummy_map[p][q]==2 && !chk[p][q]){
                                dummy_map = bfs(p,q,dummy_map);
                            }
                        }
                    }
                    calc(dummy_map);
                    map[k/m][k%m]=0;
                }
                map[j/m][j%m]=0;
            }
            map[i/m][i%m]=0;
        }

        System.out.println(answer);
    }

    public static int [][] deepCopy(int [][] dummy_map){
        for(int e1=0; e1<n; e1++ ){
            for(int e2=0; e2<m; e2++){
                dummy_map[e1][e2]=map[e1][e2];
            }
        }
        return dummy_map;
    }

    public static void resetChk(){
        for(int l=0; l<n; l++){
            Arrays.fill(chk[l],false);
        }
    }

    public static int[][] bfs(int y, int x, int [][] dummy_map) {
        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(y, x));

        dummy_map[y][x] = 2;
        chk[y][x] = true;
        while (!queue.isEmpty()) {
            Node now = queue.poll();
            for (int i = 0; i < 4; i++) {
                int now_y = now.y + diry[i];
                int now_x = now.x + dirx[i];
                if (now_y >= 0 && now_y < n && now_x >= 0 && now_x < m) {
                    if (!chk[now_y][now_x] && dummy_map[now_y][now_x] == 0) {
                        dummy_map[now_y][now_x] = 2;
                        chk[now_y][now_x] = true;
                        queue.add(new Node(now_y, now_x));
                    }
                }
            }
        }

        return dummy_map;
    }

    public static void calc(int [][] dummy_map){
        int zero_cnt=0;

        for(int i=0; i<n; i++){
            for(int j=0; j<m;j++){
                if(dummy_map[i][j]==0){
                    zero_cnt++;
                }
            }
        }
        answer = Math.max(answer,zero_cnt);
    }
}