성곽 [백준 2234][JAVA][골드 4][비트마스킹][BFS]

 

[광고 누르면 오늘의 행운 상승!!]

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

2234번: 성곽

1. 참고사항 

넘버링(컬러링)을 통해 구역을 나누어서 해결하였다.

2. 구현

- 비트마스킹을 사용하여 각 셀 4방향의 벽 중 해당하는 곳을 true로 만들어주었다.

1. 이 성에 있는 방의 개수
   - bfs를 통해 각 구역을 넘버링 하였고 bfs를 처음 시작할때 방의 갯수를 증가시켰다.
2. 가장 넓은 방의 넓이
   - bfs를 통해 방 넓이를 증가시켰고(cnt) Math.max 를 통해 최댓값을 갱신시켰다.
3. 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기
   - 넘버링 시킨 벽들을 bfs를 돌면서 옆방과 더한 값을 저장하고 Math.max를 통해 최댓값을 갱신시켰다.

 

import java.io.*;
import java.util.*;

public class Main {
	static class Player{
		int row, col;
		public Player(int row, int col) {
			this.col = col;
			this.row = row;
		}
	}

	//서북동남
	static int[] dx = {0,-1,0,1};
	static int[] dy = {-1,0,1,0};
	
	static int[][] map;
	static boolean[][] visit;
	static boolean[][][] wall;
	static int R,C,cnt,ans,roomLarge,roomCnt,roomNum,maxLarge;
	static Queue<Player> q;
	static int room[] = new int[2500];
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		C = Integer.parseInt(st.nextToken());
		R = Integer.parseInt(st.nextToken());
		//1011
		map = new int[R][C];
		wall = new boolean[4][R][C];
		visit = new boolean[R][C];
		
		for (int i = 0; i < R; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < C; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());

				for (int k = 3; k >= 0; k--) {
					if ((map[i][j] & 1 << k) >= 1)
						wall[k][i][j] = true;
				}
			}
		}

		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				if(!visit[i][j]) {
					bfs(i,j,roomNum);
					room[roomNum++] = cnt;
					roomLarge = Integer.max(roomLarge, cnt);
					maxLarge = Math.max(roomLarge, maxLarge);
				}
			}
		}
		
		visit = new boolean[R][C];
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				if(!visit[i][j]) {
					bfs2(i,j);
				}
			}
		}

		System.out.println(roomCnt);
		System.out.println(roomLarge);
		System.out.println(maxLarge);
	}
	private static void bfs2(int i, int j) {
		q = new LinkedList<>();
		visit[i][j] = true;
		q.add(new Player(i,j));
		

		while(!q.isEmpty()) {
			Player player = q.poll();
			
			for (int dir = 0; dir < 4; dir++) {
				int nx = player.row + dx[dir];
				int ny = player.col + dy[dir];
				
				if(check(nx, ny)) continue;
				
				if(!visit[nx][ny] && 
						map[player.row][player.col] != map[nx][ny]) {
					maxLarge = Math.max(maxLarge,
							room[map[player.row][player.col]] + room[map[nx][ny]]);
				}
			}
		}
	}
	private static void bfs(int i, int j, int roomNum) {
		q = new LinkedList<>();
		
		cnt = 1;
		roomCnt++;
		
		visit[i][j] = true;
		map[i][j] = roomNum;
		
		q.add(new Player(i,j));
		
		while(!q.isEmpty()) {
			Player player = q.poll();
			
			for (int dir = 0; dir < 4; dir++) {
				int nx = player.row + dx[dir];
				int ny = player.col + dy[dir];
				
				if(check(nx, ny)) continue;
				//방문하지 않았고
				if(!visit[nx][ny]) {
					//가려는곳 방향의 벽이 막혀있지 않으면
					if(!wall[dir][player.row][player.col]) {
						cnt++;
						q.add(new Player(nx,ny));
						visit[nx][ny] = true;
						map[nx][ny] = roomNum;
					} 
				}
			}
		}
	}
	private static boolean check(int nx, int ny) {
		return nx < 0 || nx >=R || ny < 0 || ny >= C;
	}
}