[BOJ] 백준 14502 - 연구소 (자바)

BFS .. DFS

문제 자체는 아주 단순한 문제이다. 바이러스가 최대한 전파되지 못하게 하는것이다. (즉 BFS나 DFS의 가지가 멀리가지 못하게 하면 된다.)

그리고 배열의 크기가 8이기 때문에 어떠한 방법을 써서 풀어도 왠만해서는 시간초과가 나지 않는다.

나는 그래서 진짜 무식하게 좌표를 일일히 계산해가며 벽을 세웠다. 진짜 못짠 코드...

풀이

1. 세개의 벽을 세운다. (벽이 설 자리는 0이 있는곳으로 세개의 벽 모두 다른 곳에 설치되어야 한다.)

   이때 벽을 설치하는 방법이 여러개가 있지만 나는 무식하게 전체 좌표를 일일히 계산했는데 인터넷에서 다른분의 코드를 보니

   0일때의 좌표를 미리 list에 저장해 논다음, list에서 빼오면 훨씬 간단히 동작한다는 것을 알게되었다.

   나는 6중 반복문을 써서 좌표를 구했지만 위의 경우 3중 반복문만 쓰면 간단히 해결 된다.

2. 세개의 벽을 모든 경우 세워보고 그때마다 BFS나 DFS로 바이러스를 퍼뜨리면 된다.

3. 나는 또 여기서 무식하게 2중 반복문으로 바이러스가 있는점을 찾았지만 이렇게 하는 것 보다 맨 처음 숫자를 입력받을 때 2의 위치를 저장해주면 2중 

   복을 계속해서 돌 필요가 없어진다. 배열이 조금만 커졋더라면 시간초과 ㅠ

4. 탐색 후 0의 갯수를 체크하여 최대 값을 저장하면 끄읏.

5. 아 그리고 벽을 세우고 바이러스를 전파했기 때문에 세개의 벽을 놓기전에 배열을 계속해서 초기화 해줘야 한다. 그래서 나는 Reset() 함수를 사용해서

   초기화시켜줌.

소스

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
 
public class Main {
    static int[] dx = { 0, 1, 0, -1 };
    static int[] dy = { 1, 0, -1, 0 };
    static int N;
    static int M;
    static int[][] arr;
    static int[][] reset;
 
    public static void main(String args[]) throws Exception {
        //BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        N = Integer.parseInt(str[0]);
        M = Integer.parseInt(str[1]);
 
        arr = new int[N][M];
        reset = new int[N][M];
        for (int i = 0; i < N; i++) {
            str = br.readLine().split(" ");
            for (int j = 0; j < M; j++) {
                arr[i][j] = Integer.parseInt(str[j]);
            }
        }
        Reset();
        int max = Integer.MIN_VALUE;
 
        for (int x1 = 0; x1 < N; x1++) {
            for (int y1 = 0; y1 < M; y1++) {
                //벽 세울 위치가 0이 아니면 패스
                if (reset[x1][y1] != 0)
                    continue;
                for (int x2 = 0; x2 < N; x2++) {
                    for (int y2 = 0; y2 < M; y2++) {
                        //좌표가 같으면 돌필요 없으므로 패스
                        if (x1 == x2 && y1 == y2)
                            continue;
                        //벽 세울 위치가 0이 아니면 패스
                        if (reset[x2][y2] != 0)
                            continue;
                        for (int x3 = 0; x3 < N; x3++) {
                            for (int y3 = 0; y3 < M; y3++) {
                                //좌표가 같으면 돌필요 없으므로 패스
                                if (x1 == x3 && y1 == y3)
                                    continue;
                                if (x2 == x3 && y2 == y3)
                                    continue;
                                //벽 세울 위치가 0이 아니면 패스
                                if (reset[x3][y3] != 0)
                                    continue;
 
                                //바이러스가 있는 점을 찾기 위한 반복문
                                for (int i = 0; i < N; i++) {
                                    for (int j = 0; j < M; j++) {
                                        //바이러스가 있을 때만 시뮬레이션 실행
                                        if (reset[i][j] == 2) {
                                            //세개의 벽을 세움
                                            reset[x1][y1] = 1;
                                            reset[x2][y2] = 1;
                                            reset[x3][y3] = 1;
                                            BFS(i, j);
                                        }
                                    }
                                }
                                max = Math.max(max, Check());
                                Reset();
                            }
                        }
                    }
                }
            }
        }
        System.out.println(max);
    }
 
    public static void BFS(int x, int y) {
        Queue<Dot> q = new LinkedList<Dot>();
        q.add(new Dot(x, y));
 
        while (!q.isEmpty()) {
            Dot d = q.poll();
            for (int i = 0; i < 4; i++) {
                int nextX = d.x + dx[i];
                int nextY = d.y + dy[i];
 
                //배열 범위를 넘어가면 패스
                if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= M) {
                    continue;
                }
                //벽에 막혀있거나 이미 바이러스에 감염됐다면 패스
                if (reset[nextX][nextY] == 1 || reset[nextX][nextY] == 2) {
                    continue;
                }
                //바이러스 전파
                q.add(new Dot(nextX, nextY));
                reset[nextX][nextY] = 2;
            }
        }
 
    }
    //다음 시뮬레이션을 해야하므로 배열을 초기화 해줘야한다.
    public static void Reset() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                reset[i][j] = arr[i][j];
            }
        }
    }
 
    //0의 계수를 체크, 즉 안전지역 개수 체크
    public static int Check() {
        int count = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (reset[i][j] == 0)
                    count++;
            }
        }
        return count;
    }
 
}
 
class Dot {
    int x;
    int y;
 
    Dot(int x, int y) {
        this.x = x;
        this.y = y;
    }
}