[백준 2234 - Java] 성곽

https://www.acmicpc.net/problem/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의 답을 출력한다.

 

풀이

이 문제는 방의 개수, 가장 큰 방의 넓이, 벽 하나를 제거해 얻을 수 있는 가장 넓은 방 크기 이렇게 3가지를 구해야합니다.

 

방의 개수와 방 크기의 경우엔 BFS알고리즘을 사용해서 벽을 확인하며 연결된 방들만을 탐색해가며 쉽게 확인이 가능합니다.

이때 저는 남, 동, 북, 서 의 순서로 벽 이있는지 확인했습니다. 

 

 

중요한 것은 벽 하나를 제거해 얻을 수 있는 가장 넓은 크기를 구하는 것입니다!

저는 앞에서 방의 넓이를 구하는 과정에서 area라는 2차원 배열을 하나 생성하여 연결된 방들 끼리는 같은 값을 갖도록 구현하였습니다. 그리고 해당 방의 크기를 ArrayList에 차례로 저장해두고 사용하였습니다.

이제 area 배열을 탐색하면서 상하좌우에 현재 방의 값과 다른 값을 갖는 방이 있는지 확인하고 있는 경우엔 그 방의 크기와 현재 방의 크기를 더해 최댓값과 비교하여 현재 합이 더 큰 경우엔 최댓값을 업데이트하는 방식으로 구현하였습니다.

 

import java.util.Scanner;
import java.util.*;

public class Main {

	static int N, M;
	static int[][] map;
	static int[] R = {0, -1, 0, 1};
	static int[] C = {-1, 0, 1, 0};
	static int[] check = {1, 2, 4, 8};
	static int[][] visited;
	static int[][] area;
	static ArrayList<Integer> areaSize = new ArrayList<>();
	static int brokenMax;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		N = sc.nextInt();
		M = sc.nextInt();
		map = new int[M][N];


		for(int i=0; i<M; i++) {
			for(int j=0; j<N; j++) {
				map[i][j] = sc.nextInt();
			}
		}

		visited = new int[M][N];
		area = new int[M][N];


		int cnt = 0;
		int maxSize = 0;

		for(int i=0; i<M; i++) {
			for(int j=0; j<N; j++) {
				//BFS
				if(visited[i][j] == 0) {
					visited[i][j] = 1;
					cnt++;
					
					Queue<Pos> q = new LinkedList<>();
					q.add(new Pos(i, j));
					int size = 0;

					while(!q.isEmpty()) {
						Pos now = q.poll();
						int wall = map[now.r][now.c];
						
						//연결된 땅들 끼리는 같은 값갖도록 넣어줌 
						area[now.r][now.c] = cnt;
						size++;

						for(int k=3; k>=0; k--) {
							int nextR = now.r+R[k];
							int nextC = now.c+C[k];

							//벽 있음 
							if(wall / check[k] > 0) {
								wall = wall%check[k];
								continue;
							}

							if(nextR<0||nextR>=M||nextC<0||nextC>=N)
								continue;

							if(visited[nextR][nextC] == 1)
								continue;


							visited[nextR][nextC] = 1;
							q.add(new Pos(nextR, nextC));
						}
					}

					if(size > maxSize)
						maxSize = size;
					
					//해당 구역의 크기 저장 
					areaSize.add(size);

				}
			}
		}


		//벽 하나 뿌시는 경우 확인
		brokenMax = 0;
		for(int i=0; i<M; i++) {
			for(int j=0; j<N; j++) {
				for(int k=0; k<4; k++) {
					int nextR = i+R[k];
					int nextC = j+C[k];

					if(nextR<0||nextR>=M||nextC<0||nextC>=N)
						continue;
					
					//둘이 벽으로 나눠진 구역인 경우 
					if(area[i][j] != area[nextR][nextC]) {
						int sum = areaSize.get(area[i][j]-1);
						sum += areaSize.get(area[nextR][nextC]-1);
						
						if(sum > brokenMax)
							brokenMax = sum;
					}
				}
			}
		}

		System.out.println(cnt);
		System.out.println(maxSize);
		System.out.println(brokenMax);

	}


	static class Pos {
		int r, c;
		Pos(int r, int c){
			this.r = r;
			this.c = c;
		}
	}

	
}