[Java/자바 백준 2234] 성곽

풀이

 

벽에 대한 숫자를 이진법으로 바꾸게 되면, 1인 곳의 방향은 벽이고 0인 곳은 연결된 공간입니다.

 

bfs로 연결된 곳을 모두 탐색하여 map에 룸의 인덱스 값을 넣어주고,

bfs 돌때마다 사이즈를 1씩 더해주어 최대 방 사이즈를 구해줍니다.

 

벽을 하나 부수어 두개의 방을 합친 최대값은,

해쉬맵을 사용해서 각 방의 크기를 넣어주고

이중 포문을 돌려 사방 탐색을 할 시에 다른 룸의 인덱스 값이 있을 때,

현재 룸 크기와 다른 룸 크기를 더해주며 max 값을 비교해주었습니다.

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

public class Main {
	static int N,M;
	static int[][] map;
	static int[][] wallMap;
	static int roomNum, roomSize, breakWallRoom;
	static HashMap<Integer, Integer> hashMap = new HashMap<>();
	// 남 동 북 서 
	static int[] dx = {1,0,-1,0};
	static int[] dy = {0,1,0,-1};
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		M = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
		
		map = new int[N][M];
		wallMap = new int[N][M];
		
		for(int i = 0 ; i < N ; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0 ; j < M ; j++) {
				wallMap[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		for(int i = 0 ; i < N ; i++) {
			for(int j = 0 ; j < M ; j++) {
				if(map[i][j] == 0) bfs(i, j, wallMap[i][j]);
			}
		}
		for(int i = 0 ; i < N ; i++) {
			for(int j = 0 ; j < M ; j++) {
				int roomIndex = map[i][j];
				for(int k = 0 ; k < 4; k++) {
					int nx = i + dx[k];
					int ny = j + dy[k];
					if(0 > nx || nx >= N || 0 > ny || ny >= M || map[nx][ny] == roomIndex) continue;
					breakWallRoom = Math.max(breakWallRoom, hashMap.get(roomIndex)+hashMap.get(map[nx][ny]));
				}
			}
		}
		System.out.println(roomNum);
		System.out.println(roomSize);
		System.out.println(breakWallRoom);
	}
	private static void bfs(int x, int y, int wall) {
		roomNum += 1;
		map[x][y] = roomNum;
		int size = 1;
		
		Queue<int[]> queue = new LinkedList<>();
		queue.offer(new int[] {x, y, wall});
		
		while(! queue.isEmpty()) {
			int cur[] = queue.poll();
			int curX = cur[0];
			int curY = cur[1];
			int curWall = cur[2];
			
			int[] dir = direction(curWall);
			
			for(int i = 0 ; i < 4; i++) {
				if(dir[i] == 1) continue;
				int nx = curX + dx[i];
				int ny = curY + dy[i];
				
				if(0 > nx || nx >= N || 0 > ny || ny >= M || map[nx][ny] != 0) continue;
				
				map[nx][ny] = roomNum;
				size += 1;
				queue.offer(new int[] {nx, ny, wallMap[nx][ny]});
			}
		}
		hashMap.put(roomNum, size);
		roomSize = Math.max(size, roomSize);
	}
	private static int[] direction(int curWall) {
		// 남 동 북 서 
		int[] dir = {0,0,0,0};
		
		for(int i = 3 ; i >= 0 ; i--) {			
			if(curWall == 0) break;
			dir[i] = curWall % 2;
			curWall /= 2;
		}
		return dir;
	}

}