문제
M x N 성곽에서 벽 정보가 비트마스크로 주어질 때, (1) 방의 개수, (2) 가장 넓은 방의 크기, (3) 벽 하나를 제거했을 때 가장 넓은 방의 크기를 구하라.
입력
첫째 줄에 N(열), M(행), 이후 M줄에 각 칸의 벽 정보(비트마스크)가 주어진다.
출력
세 줄에 걸쳐 방의 개수, 최대 방 크기, 벽 제거 시 최대 방 크기를 출력한다.
예제
| 입력 | 출력 |
|---|---|
7 4 11 6 11 6 3 10 6 7 9 6 13 5 15 5 1 10 12 7 13 7 5 13 11 10 8 10 12 13 | 5 9 16 |
풀이
BFS로 방을 탐색하여 번호와 넓이를 기록하고, 인접한 다른 방의 합으로 벽 제거 최대값을 구한다.
- 각 칸의 벽 정보를 비트 분해하여 이동 가능 방향을 판단하며 BFS로 방을 구분한다
- 각 방의 넓이를 기록하고 최대 넓이를 추적한다
- 모든 칸에 대해 인접한 다른 방이 있으면 두 방 넓이의 합을 계산하여 최대값을 갱신한다
핵심 아이디어: 벽 비트마스크에서 서/북/동/남이 각각 1/2/4/8에 대응하며, 해당 비트가 0이면 이동 가능하다.
코드
package day749;
import java.io.*;
import java.util.*;
public class Day723BOJ2234성곽 {
static int N, M;
static int max = 0;
static int[] area, dr = { 0, 1, 0, -1 }, dc = { 1, 0, -1, 0 };
static int[][] room, arr;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String[] str = br.readLine().split(" ");
N = Integer.parseInt(str[0]);
M = Integer.parseInt(str[1]);
arr = new int[M][N];
room = new int[M][N];
area = new int[2501];
for (int i = 0; i < M; i++) {
str = br.readLine().split(" ");
for (int j = 0; j < N; j++) {
arr[i][j] = Integer.parseInt(str[j]);
}
}
int c = 1;
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
if (room[i][j] == 0) {
bfs(new Pos(i, j), c);
max = Math.max(max, area[c]);
c++;
}
}
}
int sum = 0;
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
for (int k = 0; k < 4; k++) {
int nr = i + dr[k];
int nc = j + dc[k];
if ((0 <= nr && nr < M) && (0 <= nc && nc < N) && room[i][j] != room[nr][nc]) {
sum = Math.max(sum, area[room[i][j]] + area[room[nr][nc]]);
}
}
}
}
bw.write((c - 1) + "\n" + max + "\n" + sum + "\n");
bw.flush();
}
public static void bfs(Pos st, int c) {
Queue<Pos> q = new LinkedList<>();
q.offer(st);
room[st.r][st.c] = c;
while (!q.isEmpty()) {
Pos pos = q.poll();
area[c]++;
int num = arr[pos.r][pos.c];
for (int i = 0; i < 4; i++) {
Pos p;
if (num % 2 == 0) {
switch (i) {
case 0:
p = new Pos(pos.r, pos.c - 1);
break;
case 1:
p = new Pos(pos.r - 1, pos.c);
break;
case 2:
p = new Pos(pos.r, pos.c + 1);
break;
default:
p = new Pos(pos.r + 1, pos.c);
break;
}
if ((0 <= p.r && p.r < M) && (0 <= p.c && p.c < N) && room[p.r][p.c] == 0) {
q.offer(p);
room[p.r][p.c] = c;
}
}
num = num / 2;
}
}
}
static class Pos {
int r, c;
Pos(int r, int c) {
this.r = r;
this.c = c;
}
}
}복잡도
- 시간: O(NM)
- 공간: O(NM)