JAVA - [백준]14502 - 연구소

출처

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

문제

연구실에 바이러스가 퍼지고 있다. 이때, 벽을 3개만 세워 바이러스가 침투하지 못하는 안전지대 면적의 최대값을 구하는 문제이다.

풀이

벽을 세울 수 있는 모든 경우에 대해 안전지대의 값을 구하여 최대값을 구하는 방법밖에 없다는 생각이 들었다. 제약사항에 최대 넓이가 8이였기에 가능하다고 생각하였다.

3개의 벽이 세워지는 모든 경우의 수를 구하기 위해서 DFS를 사용해야 한다. 이때 벽은 3개 모두 사용해야 한다.

3개의 벽을 골랐다면, 바이러스가 퍼트려진 후 안전지대의 면적을 구해야 한다. 바이러스는 상하좌우로 퍼질 수 있다. 바이러스를 퍼트리기 위해서는 BFS를 사용할 수 있다.

이때 주의할 점은, 3개의 벽을 세운 원본 배열이 훼손되어서는 안된다. 훼손되면 다음 경우의 수 탐색이 불가능하기에 복사된 배열을 사용해야 하는데, temp = world와 같이 복사를 하게 되면 주소값을 복사하게 되어 temp 배열 수정시 world도 수정되게 된다.

우리는 이것을 얕은 복사라고 부르는데, 주소값이 아닌 값을 하나하나 복사해주는 깊은 복사를 사용해야 한다.

int[][] temp = new int[N][M];
// 깊은 복사
for (int i = 0; i < N; i++) {
	temp[i] = world[i].clone();
}
return temp;

일차원 배열은 clone()을 통해 깊은 복사를 진행할 수 있지만 우리는 이차원 배열에 대해 깊은 복사를 해야하기 때문에, 각 일차원 배열을 순회하며 clone()을 수행해주면 깊은 복사가 가능하다.

바이러스가 퍼진 후 안전지대의 수를 세고, answer에 Math.max를 통해 최대값을 갱신하며 최종적으로 구해진 answer을 출력하도록 하였다.

코드

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

public class Main {
	static int N, M, answer;
	static int[][] world;
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, 1, 0, -1};
    static Queue<Node> queue;
    


    public static void main(String[] args) throws Exception {
        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());

		world = new int[N][M];
        answer = Integer.MIN_VALUE;
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < M; j++) {
				world[i][j] = Integer.parseInt(st.nextToken());
			}
		}
        
        dfs(0);

        bw.write(answer + "\n");


        br.close();
        bw.flush();
        bw.close();
    }

    public static int[][] copyArr() {
        int[][] temp = new int[N][M];
        for (int i = 0; i < N; i++) {
            temp[i] = world[i].clone();
        }
		return temp;
    }

    public static void dfs(int cnt) {
        if (cnt == 3) {
            afterVirus();
            return;
        }

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

    public static void afterVirus() {
        queue = new LinkedList<>();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (world[i][j] == 2) {
                    queue.add(new Node(i, j));
                }
            }
        }
        int[][] temp = copyArr();

        while (!queue.isEmpty()) {
            Node n = queue.poll();
            for (int i = 0; i < 4; i++) {
                int nx = n.x + dx[i];
                int ny = n.y + dy[i];
                if (isPuttable(nx, ny, temp)) {
                    temp[nx][ny] = 2;
                    queue.add(new Node(nx, ny));
                }
            }
        }
        checkSafe(temp);
    }

    public static void checkSafe(int[][] temp) {
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (temp[i][j] == 0) {
                    cnt++;
                }
            }
        }
        answer = Math.max(answer, cnt);
    }

    public static boolean isPuttable(int x, int y, int[][] temp) {
        return x >= 0 && x < N & y >= 0 && y < M && temp[x][y] == 0;
    }

}

class Node{
	int x;
	int y;

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