[백준/자바] 2234 성곽

2234 성곽 사진 클릭 시 문제로 이동

---

문제

대략 위의 그림과 같이 생긴 성곽이 있다.

굵은 선은 벽을 나타내고, 점선은 벽이 없어서 지나다닐 수 있는 통로를 나타낸다.

이러한 형태의 성의 지도를 입력받아서 다음을 계산하는 프로그램을 작성하시오.

1. 이 성에 있는 방의 개수
2. 가장 넓은 방의 넓이
3. 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기

위의 예에서는 방은 5개고, 가장 큰 방은 9개의 칸으로 이루어져 있으며, 위의 그림에서 화살표가 가리키는 벽을 제거하면 16인 크기의 방을 얻을 수 있다.

성은 m×n(1 ≤ m, n ≤ 50) 개의 정사각형 칸으로 이루어진다.

성에는 최소 두 개의 방이 있어서, 항상 하나의 벽을 제거하여 두 방을 합치는 경우가 있다.

입력

첫째 줄에 두 정수 n, m이 주어진다.

다음 m개의 줄에는 n개의 정수로 벽에 대한 정보가 주어진다.

벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, 동쪽에 벽이 있을 때는 4를, 남쪽에 벽이 있을 때는 8을 더한 값이 주어진다.

참고로 이진수의 각 비트를 생각하면 쉽다.

따라서 이 값은 0부터 15까지의 범위 안에 있다.

출력

첫째 줄에 1의 답을, 둘째 줄에 2의 답을, 셋째 줄에 3의 답을 출력한다.

예제 입력 1

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

예제 출력 1

5
9
16

---

설명

비트마스크와 bfs를 이용한 문제다.

 

문제는 다음 3가지를 어떻게 구하냐가 관건이다.

다음 3가지 조건을 구한 변수는 다음과 같다.

1. 이 성에 있는 방의 개수 => roomCount

2. 가장 넓은 방의 넓이 => maxRoom

3. 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기 => wallRoom

 

1.

bfs를 수행한 횟수를 구하면 되기 때문에 bfs를 수행 시 roomCount++해준다.

for(int i = 0; i < m; i++) {
	for(int j = 0; j < n; j++) {
		if(!visited[i][j]) {
			bfs(i, j, roomCount);
			roomCount++;
		}
	}
}

 

2.

2021.02.10 - [알고리즘] - [알고리즘] 비트 마스크 bitmask

[알고리즘] 비트 마스크 bitmask

숫자에 해당하는 벽은 다음과 같이 볼 수 있다.

남 동 북 서

8  4  2  1

 

bfs를 수행할때 남 동 북 서를 살펴보면서 벽이 있는지 판단해야 한다.

 

한 가지 예를 들어보자.

만약 벽이 11이라면 ㄷ모양의 벽을 가지고 있다.

이때 남쪽으로 벽이 있는지 없는지 판단하고 싶다면 2의 3승이 8이기 때문에

11 & 1<<3을 수행 시 0이면 벽이 없고 1이면 벽이 존재한다는 식을 얻을 수 있다.

	남	동	북	서
11	1	0	1	1
1<<3	1	0	0	0
	1	0	0	0

가장 최대의 값으로  maxRoom를 업데이트하면 2에 해당하는 답을 구할 수 있다.

 

bfs를 수행해 이어진 칸의 수를 wallCount[0]과 wallCount [1]에 업데이트하면 해당 예제는 다음과 같은 수로 나타낼 수 있다.

for(coordiante c: back) {
	wallCount[c.x][c.y][1] = tempRoom;
	wallCount[c.x][c.y][0] = id;
}

wallCount [0] => 벽을 id 기준으로 나눈 결과

0	0	1	1	2	2	2
0	0	0	1	2	3	2
0	0	0	4	2	4	2
0	4	4	4	4	4	2

 wallCount [1] => 벽을 이어진 칸수로 나눈 결과

9	9	3	3	8	8	8
9	9	9	3	8	1	8
9	9	9	7	8	7	8
9	7	7	7	7	7	8

3.

2에서 구한 wallCount를 기준으로 상하좌우를 살폈을 때 id가 다른 경우 wallCount[1]을더해 최대의 값이 나오면 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기로 간주할 수 있다.

static void MaxRoom() {
	for(int i = 0; i < m; i++) {
		for(int j = 0; j < n; j++) {
			for(int k = 0; k < 4; k++) {
				int tx = i + dx[k];
				int ty = j + dy[k];
					
				if(tx < 0 || m <= tx || ty < 0 || n <= ty) {
					continue;
				}
					
				if(wallCount[i][j][0] != wallCount[tx][ty][0]) {
					wallRoom = Math.max(wallRoom, wallCount[i][j][1]+wallCount[tx][ty][1]);
				}
			}
		}
	}
}

 

코드