[PS] 백준 2234번 성곽

고범수·2023년 3월 7일
0

Problem Solving

목록 보기
25/31

https://www.acmicpc.net/status?user_id=rhqjatn2398&problem_id=2234&from_mine=1

문제 설명

그리드가 주어지고 각 칸의 네 방향에 벽이 있을 수 있다. 벽으로 둘러싸인 칸들이 하나의 방이 된다. 이 때, 이 성에 있는 방의 개수, 가장 넓은 방의 넓이, 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기를 구하는 문제이다.

문제 풀이

각 칸의 상태(벽의 방향별 존재유무)를 비트마스킹을 이용하여 표현하였다는 점이 흥미로운 부분이다. 각 칸에서 상하좌우 칸으로 갈 수 있는지 없는지를 비트마스킹을 이용해서 판단하여 DFS나 BFS로 탐색하면 된다. 그러면 방의 개수와 각 방의 칸 수를 알 수 있다.

이제 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기를 구하는 방법을 살펴보자.

방법은 여러가지 존재한다.

1. 모든 칸을 돌면서 칸을 직접 없애고 복구하는 방식
2. 우선 방과 칸의 개수를 그래프탐색으로 구한 후에, 모든 칸을 돌면서 현재 칸과 상하좌우의 칸이 다른 방의 칸이면 두 방의 칸 수를 합하여 구하는 방식
3. 방과 칸의 개수를 구하면서, 벽 너머의 칸을 방 번호별로 저장해둔다. 모든 방과 칸의 개수를 구했다면, 방 번호별로 저장해둔 벽 너머의 칸이 속한 방 번호를 얻을 수 있으니 방 번호가 동일한 경우를 제외하고, 두 방의 칸수를 합하여 구하는 방식

아래코드는 3번 방식으로 구한 코드이다.

import java.awt.Point;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;

	static int n, m;
	static int[][] grid, nums;
	static boolean[][] visited;
	static int[] rooms;
	static List<Point>[] adjPoints;
	static int[] dy = { 0, -1, 0, 1 };
	static int[] dx = { -1, 0, 1, 0 };

	public static void main(String[] args) throws Exception {
		st = new StringTokenizer(br.readLine());

		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());

		grid = new int[m][n];
		nums = new int[m][n];
		visited = new boolean[m][n];
		rooms = new int[2501];
		adjPoints = new List[2501];
		for (int i = 0; i < 2501; i++) {
			adjPoints[i] = new ArrayList<>();
		}

		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 roomCnt = 0;
		int maxArea = 0;
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (!visited[i][j]) {
					roomCnt++;
					visited[i][j] = true;
					nums[i][j] = roomCnt;
					rooms[roomCnt] = go(i, j, roomCnt);
					maxArea = Math.max(maxArea, rooms[roomCnt]);
				}
			}
		}

		int maxAreaOneWall = 0;
		for (int roomNum = 1; roomNum <= roomCnt; roomNum++) {
			for (Point point : adjPoints[roomNum]) {
				int adjNum = nums[point.y][point.x];

				if (adjNum == roomNum) {
					continue;
				}

				int candidate = rooms[roomNum] + rooms[adjNum];
				maxAreaOneWall = Math.max(maxAreaOneWall, candidate);
			}
		}

		System.out.println(roomCnt + "\n" + maxArea + "\n" + maxAreaOneWall);
	}

	static int go(int row, int col, int num) {
		int result = 1;

		for (int i = 0; i < 4; i++) {
			int nRow = row + dy[i];
			int nCol = col + dx[i];

			int cur = grid[row][col];
			if (inRange(nRow, nCol) && !visited[nRow][nCol]) {
				if ((cur & (1 << i)) != 0) {
					// 벽 너머의 좌표추가 같은 방이 될 좌표도 추가 될 수 있음
					adjPoints[num].add(new Point(nCol, nRow));
				} else {
					// 벽이 아니라면 같은 방
					visited[nRow][nCol] = true;
					nums[nRow][nCol] = num;
					result += go(nRow, nCol, num);
				}
			}
		}

		return result;
	}

	static boolean inRange(int row, int col) {
		return 0 <= row && row < m && 0 <= col && col < n;
	}
}

0개의 댓글