백준 2234 - 성곽

Java

2234 번 - 성곽

문제

접근 방법

최대 방 개수, 크기 구하기

0,0부터 n-1,n-1까지 탐색하여 처음 방문하는 방이면 그 위치의 방부터 시작하여 BFS로 방들의 크기를 구한다.
또한, 한번 BFS에 들어 갈 때마다 방의 개수를 세는 값을 증가시켜 방의 개수를 헤아린다.

BFS

전형적인 BFS로 인접한 방들을 탐색하면 되지만 조건이 하나 추가되었다.
이는 성곽 벽인데, 이는 문제에도 나와 있듯이 비트 연산을 통해 현재 가려는 방향에 벽이 있는지 확인하는 조건만 추가하면 된다.

하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기

유명한 BFS 문제 벽 부수고 이동하기가 떠오르지만, 실은 벽을 부수는 번거로운 방법 없이도 해결이 가능하다.
하나의 벽을 제거하여 얻는 방의 크기는, 즉 인접한 방들의 크기의 합이다.
따라서 BFS를 통해 모든 방들을 구별 한 뒤, 서로 다른 방끼리의 합을 모두 구하여 그 중 최대 값을 구하면 된다.

코드

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

public class Main {
	static int n, result, m;
	static int[][] vis;
	static int[][] wall;
	static int totalRoomCnt;
	static int maxSize;
	static int twoMaxSize;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk = new StringTokenizer(br.readLine());
    	m = stoi(stk.nextToken());
    	n = stoi(stk.nextToken());
    	vis = new int[n][m];
    	wall = new int[n][m];
    	
    	for(int i = 0; i < n; i++) {
    		stk = new StringTokenizer(br.readLine());
    		for(int j = 0; j < m; j++) {
    			wall[i][j] = stoi(stk.nextToken());
    		}
    	}
    	int idx = 1, size;
    	Map<Integer, Integer> map = new HashMap<>();
    	for(int i = 0; i < n; i++) {
    		for(int j = 0; j < m; j++) {
				// 처음 방문하는 방이면, 총 방의 개수를 늘리고, 그 방의 인덱스를 다 부여한다.
    			if(vis[i][j] == 0) {
    				totalRoomCnt++;
    				size = BFS(i,j, idx);
    				maxSize = Math.max(size, maxSize);
    				map.put(idx, size);
    				idx++;
    			}
    		}
    	}
    	System.out.println(totalRoomCnt);	// 최대 방의 개수
    	System.out.println(maxSize);		// 최대 방의 크기
		// 인접한 2개의 방 크기의 합 중 최대를 구한다.
    	int ny, nx, curR;
    	for(int i = 0; i < n; i++) {
    		for(int j = 0; j < m; j++) {
    			curR = vis[i][j];
				// 상하좌우 인접한 방 탐색
    			for(int k = 0; k < 4; k++) {
    				ny = i + dy[k];
    				nx = j + dx[k];
					// 서로 다른 방이면, 크기를 더하고 최대 크기를 갱신한다.
    				if(isIn(ny,nx) && curR != vis[ny][nx]) {
    					twoMaxSize = Math.max(twoMaxSize, map.get(curR) + map.get(vis[ny][nx]));
    				}
    			}
    		}
    	}
    	System.out.println(twoMaxSize);
    	br.close();
	}
	
	// 주어진 범위 안에 있는가
    public static boolean isIn(int y, int x){
        if(y < 0 || y >= n || x < 0 || x >= m)
            return false;
        return true;
    }
    // 서, 북, 동, 남
    static int dy[] = {0,-1,0,1};
	static int dx[] = {-1,0,1,0};
	private static int BFS(int y, int x, int idx) {
		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[] {y,x});
		vis[y][x] = idx;
		int size = 1;
		int[] q;
		int ny, nx;
		while(!queue.isEmpty()) {
			q = queue.poll();
			y = q[0];
			x = q[1];
			
			for(int i = 0; i < 4; i++) {
				// 현재 가려는 방향에 벽이 없으면 이동이 가능하다.
				if((wall[y][x] >> i & 1) == 0) {
					ny = y + dy[i];
					nx = x + dx[i];
					// 아직 방문하지 않은 방이면 방문하고 방 크기 측정 값을 증가시킨다.
					if(isIn(ny,nx) && vis[ny][nx] == 0) {
						size++;
						queue.add(new int[] {ny,nx});
						vis[ny][nx] = idx;
					}
				}
			}
		}
		return size;
	}
	
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

개선할 점