[백준 / Java] 14502번: 연구소 (골드4)

문제 풀이 날짜: 2023.09.25
포스트 작성일: 2023.09.30

 

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

 

문제 출처

백준 온라인 저지 14502번: 연구소 (골드4)

 

키워드

백트래킹(조합), BFS

 

풀이 접근법

• 백트래킹(가지치기) + BFS 문제
  •  3 ≤ N, M ≤ 8 이므로 최대 64개의 칸 중에서 3개의 칸을 선정한다.
  • 즉, 재귀의 depth가 3으로 고정된다. ⇒ 입력이 커도 재귀 백트래킹이 가능한 사례
  • 항상 3개의 벽을 세울 수 있는 경우만 입력으로 주어진다.
• 조합으로 벽을 3개씩 세울 때마다 감염되지 않은 칸이 몇 개인지 BFS로 센다. (flood fill)
• 주의: 벽에 막혀서 방문하지 못한 칸이 존재하더라도(false) 해당 칸의 숫자가 0이면 안전지역이다.
  • 따라서 감염 처리를 하는 배열을 따로 생성하고(≠visited), 감염되지 않은 칸만 세주었다.

 

코드

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	private static final int EMPTY = 0;
	private static final int VIRUS = 2;

	private static int N;
	private static int M;

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

	private static int[][] matrix;

	private static List<Point> points = new ArrayList<>();
	private static List<Point> viruses = new ArrayList<>();

	private static int safeArea = 0;

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

		String[] temp = br.readLine().split(" ");

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

		matrix = new int[N][M];

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

				if (matrix[i][j] == EMPTY) {
					points.add(new Point(j, i));
				}

				if (matrix[i][j] == VIRUS) {
					viruses.add(new Point(j, i));
				}
			}
		}

		combination(0, 0);

		System.out.print(safeArea);
	}

	private static void combination(int depth, int lastIndex) {
		if (depth == 3) {
			int[][] copied = new int[N][M];
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					copied[i][j] = matrix[i][j];
				}
			}

			for (Point start : viruses) {
				BFS(start, copied);
			}

			int sum = 0;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if (copied[i][j] == EMPTY)
						sum += 1;
				}
			}

			safeArea = Math.max(sum, safeArea);
			return;
		}

		for (int i = lastIndex; i < points.size(); i++) {
			Point p = points.get(i);
			matrix[p.y][p.x] = 1;
			combination(depth + 1, i + 1);
			matrix[p.y][p.x] = 0;
		}
	}

	private static void BFS(Point start, int[][] copied) {
		Queue<Point> queue = new ArrayDeque<>();

		queue.add(start);

		while (!queue.isEmpty()) {
			Point p = queue.poll();

			int nr = 0;
			int nc = 0;
			for (int i = 0; i < dr.length; i++) {
				nr = p.y + dr[i];
				nc = p.x + dc[i];

				if (!isValid(nr, nc)) {
					continue;
				}

				if (copied[nr][nc] == EMPTY) {
					copied[nr][nc] = VIRUS;
					queue.add(new Point(nc, nr));
				}
			}
		}

		return;
	}

	private static boolean isValid(int nr, int nc) {
		return (nr > -1 && nc > -1 && nr < N && nc < M);
	}

}

 

---