[Baekjoon] 14502번: 연구소 - Java

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

14502번: 연구소

문제 설명

벽 3개를 모두 사용하여 안전 구역을 최대한 많이 만드는 문제이다.

풀이 방법

DFS와 BFS를 혼합하여 사용한다.

먼저 DFS로 벽을 세우고, BFS로는 바이러스를 전파한다. 그렇게 만들어진 안전 구역을 구해가면서 최댓값을 구한다.

먼저 DFS 코드부터 확인하자.

private static void buildWall(int count) {
    if (count == 3) {
        processMainLogic(); // 처참한 네이밍 수준..
        return;
    }

    for (int x = 0; x < N; x++) {
        for (int y = 0; y < M; y++) {
            if (map[x][y] == SPACE) {
                map[x][y] = WALL;
                buildWall(count + 1);
                map[x][y] = SPACE;
            }
        }
    }
}

3개의 벽을 모두 세우고 나면 바이러스를 퍼뜨린다. 그전에 해야 할 사항들이 있다.

private static void processMainLogic() {
    copyMapToTmp();
    findSourceOfVirus();
    spreadVirus();
    calcMax();
}

먼저 임시 맵으로 원본 맵을 복사한다.복사 한다. 복사하는 이유는 원본을 바꾸지 않기 위함이다. 원본 맵으로 하게 되면 바이러스를 퍼뜨리고 나서 다시 전부 안전 구역으로 바꾸는 작업을 해줘야 한다. 이런 불필요한 작업을 하지 않기 위해 임시 맵으로 복사한다.

private static void copyMapToTmp() {
    for (int x = 0; x < N; x++)
        for (int y = 0; y < M; y++)
            tmp[x][y] = map[x][y];
}

그리고 바이러스의 근원지를 찾아서 큐에 넣는다.

private static void findSourceOfVirus() {
    // 큐는 전역변수
    virusQueue.clear();

    for (int x = 0; x < N; x++)
        for (int y = 0; y < M; y++)
            if (tmp[x][y] == VIRUS)
                virusQueue.offer(Position.of(x, y));
}

이제 BFS로 바이러스를 퍼뜨린다.

private static void spreadVirus() {
    while (!virusQueue.isEmpty()) {
        Position position = virusQueue.poll();
        for (int i = 0; i < 4; i++) {
            int nextX = position.getX() + dx[i];
            int nextY = position.getY() + dy[i];

            if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= M)
                continue;

            if (tmp[nextX][nextY] == SPACE) {
                tmp[nextX][nextY] = VIRUS;
                virusQueue.offer(Position.of(nextX, nextY));
            }
        }
    }
}

갈 수 있는 모든 구역에 바이러스가 퍼졌으면 이제 안전 구역을 세고 최댓값을 구한다.

private static void calcMax() {
    ans = Math.max(ans, countSafeArea());
}

private static int countSafeArea() {
    int count = 0;
    for (int x = 0; x < N; x++)
        for (int y = 0; y < M; y++)
            if (tmp[x][y] == SPACE)
                count++;

    return count;
}

전체 코드는 다음과 같다.

package baekjoon.dfs_bfs;

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

public class BOJ14502 {

    static int N;
    static int M;
    static int ans = Integer.MIN_VALUE;
    static int[][] map;
    static int[][] tmp;
    static final int[] dx = {-1, 1, 0, 0};
    static final int[] dy = {0, 0, -1, 1};
    static final int SPACE = 0;
    static final int WALL = 1;
    static final int VIRUS = 2;
    static final Queue<Position> virusQueue = new LinkedList<>();

    public static void main(String[] args) throws IOException {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            String[] split = br.readLine().split(" ");

            N = Integer.parseInt(split[0]);
            M = Integer.parseInt(split[1]);

            map = new int[N][M];
            tmp = new int[N][M];

            createMap(br);
            solution();

            System.out.println(ans);
        }
    }

    private static void createMap(BufferedReader br) throws IOException {
        for (int x = 0; x < N; x++) {
            int[] line =
                    Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            for (int y = 0; y < M; y++) {
                map[x][y] = line[y];
            }
        }
    }

    private static void solution() {
        simulate();
    }

    private static void simulate() {
        buildWall(0);
    }

    private static void buildWall(int count) {
        if (count == 3) {
            processMainLogic(); // 처참한 네이밍 수준..
            return;
        }

        for (int x = 0; x < N; x++) {
            for (int y = 0; y < M; y++) {
                if (map[x][y] == SPACE) {
                    map[x][y] = WALL;
                    buildWall(count + 1);
                    map[x][y] = SPACE;
                }
            }
        }
    }

    private static void processMainLogic() {
        copyMapToTmp();
        findSourceOfVirus();
        spreadVirus();
        calcMax();
    }

    private static void copyMapToTmp() {
        for (int x = 0; x < N; x++)
            for (int y = 0; y < M; y++)
                tmp[x][y] = map[x][y];
    }

    private static void findSourceOfVirus() {
        virusQueue.clear();

        for (int x = 0; x < N; x++)
            for (int y = 0; y < M; y++)
                if (tmp[x][y] == VIRUS)
                    virusQueue.offer(Position.of(x, y));
    }

    private static void spreadVirus() {
        while (!virusQueue.isEmpty()) {
            Position position = virusQueue.poll();
            for (int i = 0; i < 4; i++) {
                int nextX = position.getX() + dx[i];
                int nextY = position.getY() + dy[i];

                if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= M)
                    continue;

                if (tmp[nextX][nextY] == SPACE) {
                    tmp[nextX][nextY] = VIRUS;
                    virusQueue.offer(Position.of(nextX, nextY));
                }
            }
        }
    }

    private static void calcMax() {
        ans = Math.max(ans, countSafeArea());
    }

    private static int countSafeArea() {
        int count = 0;
        for (int x = 0; x < N; x++)
            for (int y = 0; y < M; y++)
                if (tmp[x][y] == SPACE)
                    count++;

        return count;
    }


    static class Position {
        private int x;
        private int y;

        private Position(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public int getX() {
            return x;
        }

        public int getY() {
            return y;
        }

        public static Position of(int x, int y) {
            return new Position(x, y);
        }
    }
}