[BOJ] 14502번 연구소 - JAVA

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

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

public class Main {
	static class Pos {
		int r;
		int c;

		public Pos(int r, int c) {
			super();
			this.r = r;
			this.c = c;
		}

	}

	static int[] dr = { -1, 1, 0, 0 };
	static int[] dc = { 0, 0, -1, 1 };

	static int N, M, max = Integer.MIN_VALUE;
	static int[][] map;
	static int[][] copy;

	static int[] indexes = new int[3];

	static ArrayList<Pos> candidates = new ArrayList<>();
	static ArrayList<Pos> viruses = new ArrayList<>();
	static Queue<Pos> q;

	public static void main(String[] args) throws IOException {
		init();
		comb(0, 0);
		print();
	}

	private static void init() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new int[N][M];
		copy = new int[N][M];

		// 입력 받으면서 벽을 세울 수 있는 구역의 리스트와 바이러스 리스트에 담기
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if (map[i][j] == 0) {
					candidates.add(new Pos(i, j));
				}
				if (map[i][j] == 2) {
					viruses.add(new Pos(i, j));
				}
			}
		}
	}

	private static void comb(int depth, int now) {
		if (depth == 3) {
			copyMap();
			build();
			spread();
			updateMax();
			return;
		}
		for (int i = now; i < candidates.size(); i++) {
			indexes[depth] = i;
			comb(depth + 1, i + 1);
		}
	}


	private static void copyMap() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				copy[i][j] = map[i][j];
			}
		}
	}

	private static void build() {
		for (int i : indexes) {
			Pos now = candidates.get(i);
			copy[now.r][now.c] = 1;
		}
	}

	private static void spread() {
		for (Pos virus : viruses) {
			bfs(virus);
		}
	}

	private static void bfs(Pos start) {
		q = new LinkedList<>();
		q.add(start);
		while (!q.isEmpty()) {
			Pos now = q.poll();
			for (int i = 0; i < 4; i++) {
				int nr = now.r + dr[i];
				int nc = now.c + dc[i];
				if (nr < 0 || nc < 0 || nr >= N || nc >= M)
					continue;
				if (copy[nr][nc] == 1 || copy[nr][nc] == 2)
					continue;
				copy[nr][nc] = 2;
				q.add(new Pos(nr, nc));
			}
		}
	}

	private static void updateMax() {
		max = Math.max(max, countSafe());
	}

	private static int countSafe() {
		int cnt = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (copy[i][j] == 0) {
					cnt++;
				}
			}
		}
		return cnt;
	}

	private static void print() {
		System.out.println(max);
	}
}

📄 해설

• 조합과 BFS 를 같이 사용하여 해결하였음

절차

1. 입력받으면서 지도의 위치를 저장하는 빈칸 리스트와 바이러스 리스트를 생성
2. 빈칸 리스트 중에서 벽을 세울 조합을 생성하고, 벽을 세움(벽은 3개까지만 세울 수 있음)
   • 이 작업은 지도의 복사본에서 수행해야함
3. 완성된 복사본 지도에서 바이러스들의 확산을 수행함
4. 확산이 끝난 후, 안전 구역의 개수를 세고, 최솟값을 갱신