[백준] 14502 연구소 - Implementation / Java

• 문제 링크

14502번: 연구소

 

• 풀이 과정

연구소에 벽을 3개 세우는 모든 경우의 수를 재귀적으로 dfs 를 통해 구한다.

이렇게 벽을 세운 각각의 경우의 바이러스 확산을  bfs 를 통해 구현하고

이때 바이러스를 확산시킬 공간은 기존 lab 배열을 복사한 copy 배열을 생성해 구현한다.

 

바이러스가 확산된 copy 배열을 매개변수로 받아 해당 배열에 존재하는 0의 개수,

즉 안전 영역의 크기를 배열을 전체 탐색하여 구하고

이를 매번 maxCnt와 비교하여 최댓값으로써 갱신하여 정답을 출력한다.

 

• 풀이 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static int n, m;
	static int[][] lab;
	static int[] dy = { -1, 1, 0, 0 };
	static int[] dx = { 0, 0, -1, 1 };
	static int maxCnt = Integer.MIN_VALUE;

	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());
		lab = new int[n][m];

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < m; j++)
				lab[i][j] = Integer.parseInt(st.nextToken());
		}

		dfs(0);

		bw.write(maxCnt + "\n");
		bw.flush();
	}

	private static void dfs(int wall) {
		if (wall == 3) {
			bfs();
			return;
		}

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (lab[i][j] == 0) {
					lab[i][j] = 1;
					dfs(wall + 1);
					lab[i][j] = 0;
				}
			}
		}
	}

	private static void bfs() {
		Queue<Node> q = new LinkedList<>();

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (lab[i][j] == 2)
					q.offer(new Node(i, j));
			}
		}

		int[][] copy = new int[n][m];
		for (int i = 0; i < n; i++)
			copy[i] = lab[i].clone();

		while (!q.isEmpty()) {
			Node now = q.poll();
			for (int i = 0; i < 4; i++) {
				int ny = now.y + dy[i];
				int nx = now.x + dx[i];

				if (ny >= 0 && nx >= 0 && ny < n && nx < m) {
					if (copy[ny][nx] == 0) {
						q.offer(new Node(ny, nx));
						copy[ny][nx] = 2;
					}
				}
			}
		}

		safe(copy);
	}

	private static void safe(int[][] copy) {
		int cnt = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (copy[i][j] == 0)
					cnt++;
			}
		}

		if (maxCnt < cnt)
			maxCnt = cnt;
	}

	private static class Node {
		int y;
		int x;

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

}