[백준 2234] 성곽 - JAVA

문제 링크 : https://www.acmicpc.net/problem/2234

문제 정의

• 성의 지도가 주어지고 구분된 공간을 방이라고 합니다.
• 각 좌표는 각각 1의 공간이라 했을 때
• 방의 수, 방의 최대 넓이, 벽을 하나 뚫었을 때 최대 넓이를 구해라

---

접근 방법

방 구분 방법

우선 Flood Fill로 각 방을 구분해야합니다.

입력으로는 해당 위치의 벽이 주어지기 때문에
방을 나눌 별도의 2차원 배열인 mapIndex를 선언해주었습니다.

---

방문 조건 로직

BFS를 통해
ny nx를 구하고 visited를 통해 처리하는 기존 문제랑은 달리

상/하/좌/우를 탐색하고 다음의 조건을 충족해야 합니다.

• 성의 영역 내인가? inBound()
• 다른 방의 영역인가? isNotOtherRoom()
• 이동할 방향에 벽이 존재하는가? isNotWall()
• 방문한 적이 있는가? isNotVisited()

이 네 가지 조건을 충족하게 된다면
현재 방의 새로운 공간으로 인정하게 됩니다.

---

출력 로직

방의 수 구하기

방은 Flood Fill을 수행하는 도중에 동적으로 추가되기 때문에
roomSpaceList는Array가 아닌 List로 구현했습니다.

roomSpaceList는 0부터 시작하지만 방의 인덱스는 1부터 시작하므로
방의 수는 `roomSpaceList.size -1이 되어야 합니다.

---

방의 최대 넓이 구하기

roomSpaceList를 순회하며 넓이가 최대인 것을 출력합니다.

벽을 하나 뚫었을 때 최대 넓이 구하기

현재 방과 인접한 방의 인덱스는 BFS 도중에 저장하기 위해
가변 공간이 필요했고
하나의 방이 여러번 같은 인접한 방을 접근 할 수 있으므로
HashSet으로 중복 제거했습니다.

또한 추후 벽을 부순 공간의 넓이를 구할 때

• 방1 -> 방2를 부실 때
• 방2 -> 방1을 부실 때

이 두 가지는 같은 값을 가지므로
단방향으로 값을 저장하도록 구현했습니다.

이후 각 방과 인접한 방들의 넓이들을 계산하며 최댓값을 출력합니다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.*;

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

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static List<Integer> roomSpaceList;
	static List<Set<Integer>> nearRoomList;
	static int[] dy = {0, 1, 0, -1};
	static int[] dx = {1, 0, -1, 0};
	static int[][] castleMap;
	static int[][] mapIndex;
	static int M;
	static int N;

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

		System.out.println(getRoomCount());
		System.out.println(getMaxArea());
		System.out.println(getBreakOneWallMaxArea());
	}

	private static int getBreakOneWallMaxArea() {
		int max = 0;
		for (int i = 1; i < nearRoomList.size(); i++) {
			int baseArea = roomSpaceList.get(i);
			for (int target : nearRoomList.get(i)) {
				int sumArea = baseArea + roomSpaceList.get(target);
				max = Math.max(max, sumArea);
			}
		}
		return max;
	}


	private static int getMaxArea() {
		int max = 0;
		for (int i = 1; i < roomSpaceList.size(); i++) {
			max = Math.max(max, roomSpaceList.get(i));
		}
		return max;
	}

	static int getRoomCount() {
		return roomSpaceList.size() - 1;
	}

	static void floodFill() {
		int index = 1;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (mapIndex[i][j] == 0) {
					bfs(i, j, index);
					index++;
				}
			}
		}
	}

	static void bfs(int i, int j, int index) {
		int space = 0;
		nearRoomList.add(new HashSet<>());

		ArrayDeque<Node> q = new ArrayDeque<>();
		q.offer(new Node(i, j));
		mapIndex[i][j] = index;

		while (!q.isEmpty()) {
			Node node = q.poll();
			int y = node.y;
			int x = node.x;

			for (int d = 0; d < 4; d++) {
				int ny = y + dy[d];
				int nx = x + dx[d];

				if (inbound(ny, nx) && isNotOtherRoom(ny, nx, index) && isNotWall(ny, nx, d) && isNotVisited(ny, nx)) {
					mapIndex[ny][nx] = index;
					q.offer(new Node(ny, nx));
				}
			}
			space++;
		}

		roomSpaceList.add(space);
	}

	static boolean isNotVisited(int ny, int nx) {
		return mapIndex[ny][nx] == 0;
	}

	static boolean isNotOtherRoom(int ny, int nx, int index) {
		if (mapIndex[ny][nx] != 0 && mapIndex[ny][nx] != index) {
			nearRoomList.get(index).add(mapIndex[ny][nx]);
			return false;
		}
		return true;
	}

	private static boolean isNotWall(int ny, int nx, int d) {
		return (castleMap[ny][nx] & (1 << d)) == 0;
	}

	static boolean inbound(int ny, int nx) {
		return 0 <= ny && ny < N && 0 <= nx && nx < M;
	}

	static void init() throws IOException {
		roomSpaceList = new ArrayList<>();
		nearRoomList = new ArrayList<>();

		roomSpaceList.add(0);
		nearRoomList.add(new HashSet<>());

		st = new StringTokenizer(br.readLine());
		M = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());

		castleMap = new int[N][M];
		mapIndex = new int[N][M];

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