[백준] 2234번: 성곽

문제

[백준] 2234번: 성곽

분석

격자에 각 칸마다 주변 벽 정보가 주어질 때, 다음의 세 값을 구하는 문제이다.
1.이 성에 있는 방의 개수
2.가장 넓은 방의 넓이
3.하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기

N과 M이 각각 최대 50이므로 BFS나 DFS를 통해 탐색해도 충분히 통과할 수 있다.
문제에서 벽의 정보를 서:1, 북:2, 동:4, 남:8로 주기 때문에 이를 잘 관찰하면 2^0, 2^1, 2^2, 2^3으로 비트 연산을 이용하면 연산하기 편할 것으로 보인다.

해당 방향에 벽이 없는지 판별하기 위해서는 격자의 값과 & 연산을 해서 0인지를 보면 된다.
이렇게 dfs를 이용하면 1,2는 쉽게 구할 수 있다.
그러나 3을 구할 때 (벽을 하나 뚫을 수 있다는 조건이 주어졌을 때), 과거의 풀이 방식을 보면 bfs로 진행하면서 visited를 3차원으로 만들어 뚫을 수 있는 경우를 나누어 진행했다. 그러나 이렇게 진행하면 bfs의 반복 횟수가 너무 많아지므로 시간 초과가 날 수도 있다. 따라서 dfs를 진행할 때 각 격자에 방 번호를 매기고 dfs가 끝났을 때, 벽을 둔 격자만 조사하여 서로 방 번호가 다를 때 각 크기를 합산해 주어 3번을 구할 수 있게 된다.

DFS를 활용한 코드이므로 격자를 탐색하는 O(N*M)이 시간 복잡도이다.

코드

해결언어 : Java

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	static int M, N, size, mx2, mx3;
	static int[][] grid, room;
	static int[] roomSize;
	static int[] dx = { 0, -1, 0, 1 }; // 2^0, 2^1, 2^2, 2^3
	static int[] dy = { -1, 0, 1, 0 };

	public static void main(String[] args) 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());
		grid = new int[M][N];
		room = new int[M][N];
		roomSize = new int[M * N + 1];
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				grid[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		int num = 0;
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				if (room[i][j] == 0) {
					num += 1;
					size = 0;
					dfs(i, j, num);
					roomSize[num] = size;
				}
			}
		}
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				for (int d = 0; d < 4; d++) {
					if ((grid[i][j] & (1 << d)) != 0) {
						int ni = i + dx[d];
						int nj = j + dy[d];
						if (in_range(ni, nj)) {
							if (room[i][j] != room[ni][nj]) {
								mx3 = Math.max(mx3, roomSize[room[i][j]] + roomSize[room[ni][nj]]);
							}
						}
					}
				}
			}
		}
		System.out.println(num);
		System.out.println(mx2);
		System.out.println(mx3);
		br.close();
	}

	static void dfs(int x, int y, int num) {
		room[x][y] = num;
		size += 1;
		mx2 = Math.max(mx2, size);
		int val = grid[x][y];
		for (int i = 0; i < 4; i++) {
			if ((val & (1 << i)) == 0) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				if (in_range(nx, ny) && room[nx][ny] == 0)
					dfs(nx, ny, num);
			}
		}
	}

	static boolean in_range(int x, int y) {
		return 0 <= x && x < M && 0 <= y && y < N;
	}

}