[Baekjoon Online Judge] 2234 - 성곽 / Java

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

2234번: 성곽

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

public class Main {

	static int N, M, max = 0;
	static int[][] map;
	static boolean[][] visited;

	// 서북동남 좌상우하
	static int[] dr = { 0, -1, 0, 1 };
	static int[] dc = { -1, 0, 1, 0 };

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new int[M][N];
		visited = new boolean[M][N];

		// map 입력받기
		for (int r = 0; r < M; r++) {
			st = new StringTokenizer(br.readLine());

			for (int c = 0; c < N; c++) {
				map[r][c] = Integer.parseInt(st.nextToken());
			}
		}

		// 1. 이 성에 있는 방의 개수
		// 2. 가장 넓은 방의 넓이
		int room = 0;

		for (int r = 0; r < M; r++) {
			for (int c = 0; c < N; c++) {
				if (!visited[r][c]) {
					bfs(r, c);
					room++;
				}
			}
		}

		sb.append(room).append("\n").append(max).append("\n");

		// 3. 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기
		for (int r = 0; r < M; r++) {
			for (int c = 0; c < N; c++) {
				// 사방탐색
				for (int bit = 1; bit <= 8; bit <<= 1) {
					// 현재 방향으로 갈 수 있는 경우
					// 0인 경우: bit 방향에 벽 없음
					// 0이 아닌 경우: bit 방향에 벽 있음
					if ((map[r][c] & bit) != 0) {
						visited = new boolean[M][N];
						// 벽 제거
						map[r][c] -= bit;

						bfs(r, c);

						// 다시 벽 세우기
						map[r][c] += bit;
					}
				}
			}
		}

		sb.append(max);

		System.out.println(sb);
	}

	private static void bfs(int r, int c) {
		Queue<int[]> q = new LinkedList<>();

		q.add(new int[] { r, c });
		visited[r][c] = true;

		int cRoom = 1, cr, cc, nr, nc, bit, curr[];

		while (!q.isEmpty()) {
			curr = q.poll();
			cr = curr[0];
			cc = curr[1];
			bit = 1;

			for (int dir = 0; dir < 4; dir++) {
				if ((map[cr][cc] & bit) == 0) {					
					nr = cr + dr[dir];
					nc = cc + dc[dir];

					// 경계 안에 있고 아직 방문하지 않은 경우
					if ((nr >= 0 && nr < M && nc >= 0 && nc < N) && !visited[nr][nc]) {
						// 방의 개수 + 1
						cRoom++;
						visited[nr][nc] = true;
						q.add(new int[] { nr, nc });
					}
				}
				// 1 2 4 8
				bit <<= 1;
			}
		}

		// 최댓값과 현재 방의 개수 비교
		max = Math.max(max, cRoom);
	}
}