[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의 답을 출력한다.

https://www.acmicpc.net/problem/2234

2234번: 성곽

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main
{
	static int MAP[][];
	static int MY[][];
	static String TWO[][];
	static int CNT[][];
	static boolean VISIT[][];
	
	static char[] BIN;
	static int[] dx = { 1, 0, -1, 0 };
	static int[] dy = { 0, 1, 0, -1 };

	static int M, N, ROOM, RANGE, MAX, OPEN;
	static HashMap<Integer, Integer> HM;

	public static void main(String[] args)
	{
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();

		MAP = new int[M][N];
		MY = new int[M][N];
		CNT = new int[M][N];
		TWO = new String[M][N];
		VISIT = new boolean[M][N];
		HM = new HashMap<Integer, Integer>();
		ROOM = 0;
		MAX = Integer.MIN_VALUE;

		for (int i = 0; i < M; i++)
		{
			for (int j = 0; j < N; j++)
			{
				MAP[i][j] = sc.nextInt();
				String str = Integer.toBinaryString(MAP[i][j]);
				while(str.length() < 4)
				{
					str = '0' + str;
				}
				TWO[i][j] = str;
			}
		}

		// 방갯수 체크 및 지도 만들기
		for (int i = 0; i < M; i++)
		{
			for (int j = 0; j < N; j++)
			{
				if (!VISIT[i][j])
				{
					ROOM++;
					bfs(i, j);
					MAX = Math.max(MAX, RANGE);
					HM.put(ROOM, RANGE);
				}
			}
		}
		
		/*
		// 방갯수 맵 만들기
		for (int i = 0; i < M; i++)
		{
			for (int j = 0; j < N; j++)
			{
				int roomNo = MY[i][j];
				int roomCnt = HM.get(roomNo);

				CNT[i][j] = roomCnt;
			}
		}
		*/

		OPEN = Integer.MIN_VALUE;
		VISIT = new boolean[M][N];
		for (int i = 0; i < M; i++)
		{
			for (int j = 0; j < N; j++)
			{
				VISIT[i][j] = true;
				for (int k = 0; k < 4; k++)
				{
					int nextX = i + dx[k];
					int nextY = j + dy[k];

					if (nextX < 0 || nextY < 0 || nextX >= M || nextY >= N)
						continue;
					if (VISIT[nextX][nextY])
						continue;

					VISIT[nextX][nextY] = true;

					if (MY[nextX][nextY] == MY[i][j])
						continue;
					else {
						int roomNo = MY[i][j];
						int roomCnt = HM.get(roomNo);
						int roomNo2 = MY[nextX][nextY];
						int roomCnt2 = HM.get(roomNo2);
						
						OPEN = Math.max(OPEN, roomCnt+roomCnt2);
					}
				}
			}
		}

		System.out.println(ROOM);
		System.out.println(MAX);
		System.out.println(OPEN);
	}

	private static void printROOM()
	{
		System.out.println();
		for (int i = 0; i < M; i++)
		{
			System.out.println();
			for (int j = 0; j < N; j++)
			{
				System.out.print(MY[i][j] + " ");
			}
		}
		System.out.println();
	}

	private static void bfs(int x, int y)
	{
		RANGE = 1;

		Queue<POSITION> q = new LinkedList<POSITION>();
		VISIT[x][y] = true;
		MY[x][y] = ROOM;
		q.offer(new POSITION(x, y));

		while (!q.isEmpty())
		{
			POSITION p = q.poll();
			//change(p.x, p.y);
			BIN = TWO[p.x][p.y].toCharArray();

			for (int i = 0; i < 4; i++)
			{
				int nextX = p.x + dx[i];
				int nextY = p.y + dy[i];

				if (nextX < 0 || nextY < 0 || nextX >= M || nextY >= N)
					continue;
				if (VISIT[nextX][nextY])
					continue;

				if (BIN[i] == '0')
				{
					MY[nextX][nextY] = ROOM;
					VISIT[nextX][nextY] = true;
					RANGE++;
					q.offer(new POSITION(nextX, nextY));
				}
			}
		}
	}

	private static void change(int px, int py)
	{
		int len1 = TWO[px][py].length();
		if (len1 < 4)
		{
			for (int i = 0; i < 4 - len1; i++)
			{
				BIN[i] = '0';
			}
			int j = 0;
			for (int i = 4 - len1; i < 4; i++)
			{
				BIN[i] = TWO[px][py].charAt(j);
				j++;
			}
		} else
		{
			BIN = TWO[px][py].toCharArray();
		}
	}

	private static void printTWO()
	{
		for (int i = 0; i < M; i++)
		{
			System.out.println();
			for (int j = 0; j < N; j++)
			{
				System.out.print(TWO[i][j] + " ");
			}
		}
	}

}

class POSITION
{
	int x;
	int y;

	POSITION(int x, int y)
	{
		this.x = x;
		this.y = y;
	}
}