백준 14502 연구소(JAVA)

문제 설명

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

 

풀이과정

 총 3단계로 나눠서 풀이했다. 먼저, 벽 3개를 짓는다. 다음으로 바이러스를 퍼뜨린다. 마지막으로 안전 영역을 카운팅한다. 바이러스를 퍼뜨릴 때 원래 board를 보존하기 위해서 newBoard라는 새로운 변수를 사용했고, DFS를 이용해서 바이러스를 퍼뜨렸다.

 

정답코드

import java.io.*;
import java.util.*;

public class Main {

    static int[] dy = {-1, 1, 0, 0};
    static int[] dx = {0, 0, -1, 1};
    static int N, M;
    static int[][] board;
    static int[][] newBoard;
    static int result = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        board = new int[N][M];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < M; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 1. 벽을 3개 세운다.
        // 2. 바이러스가 퍼진다.
        // 3. 안전영역을 센다.

        createWall(0);

        bw.write(String.valueOf(result));
        bw.flush();
    }

    public static void createWall(int wall) {
        if (wall == 3) {
            virus();
            return;
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (board[i][j] == 0) {
                    board[i][j] = 1;
                    createWall(wall + 1);
                    board[i][j] = 0;
                }
            }
        }
    }

    public static void virus() {
        newBoard = new int[N][M];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                newBoard[i][j] = board[i][j];
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (newBoard[i][j] == 2) {
                    dfs(i, j);
                }
            }
        }

        int cnt = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (newBoard[i][j] == 0) {
                    cnt++;
                }
            }
        }

        result = Math.max(result, cnt);
    }

    public static void dfs(int y, int x) {
        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];

            if (ny >= 0 && ny < N && nx >= 0 && nx < M) {
                if (newBoard[ny][nx] == 0) {
                    newBoard[ny][nx] = 2;
                    dfs(ny, nx);
                }
            }
        }
    }
}