백준 2234 : 성곽

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

2234번: 성곽

[ 문제풀이 ]

서북동남 순서로 1,2,4,8의 값을 가지기 때문에 (1~4)번째 bit가 1인지를 확인해주면 벽이 존재하는지 판단할 수 있다.

따라서 dfs + 비트마스킹을 통해 탐색하면서 방마다 인덱스를 매겨주고 각 방의 넓이를 저장해준다. 이렇게 하면 1, 2번을 해결할 수 있다.

3번을 해결하기 위해서 벽을 제거하였는지를 판단하는 변수를 하나 두고 dfs를 수행해도 되지만 어차피 벽들은 붙어있기 때문에 모든 좌표를 탐색하면서 현재 방에서 인접한 방 중 가장 넓은 방의 인덱스를 저장해주면 해결할 수 있다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

	static int n, m, idx, cnt;
	static List<Integer> area;
	static int[][] map, visit;
	static int[][] dir = {{0,-1},{-1,0},{0,1},{1,0}};
	
	public static void main(String[] args) {
		try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
				BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			n = Integer.parseInt(st.nextToken());
			m = Integer.parseInt(st.nextToken());
			map = new int[m][n];
			visit = new int[m][n];
			for (int i = 0; i < m; ++i) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < n; ++j) {
					map[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			
			area = new ArrayList<>(Arrays.asList(0));
            		//dfs를 수행하면서 방에 번호를 매겨줌
			for (int i = 0; i < m; ++i) {
				for (int j = 0; j < n; ++j) {
					if (visit[i][j] != 0) continue;
					idx++; cnt = 0;
					dfs(i, j);
					area.add(cnt);
				}
			}
			
            		//모든 좌표를 탐색하면서 인접한 방 중 가장 넓은 방의 크기를 저장
			int[] near = new int[idx + 1];
			for (int i = 0; i < m; ++i) {
				for (int j = 0; j < n; ++j) {
					for (int d = 0; d < 4; ++d) {
						int ny = i + dir[d][0];
						int nx = j + dir[d][1];
						if (ny < 0 || nx < 0 || ny >= m || nx >= n) continue;
						if (visit[ny][nx] == visit[i][j]) continue;
						near[visit[i][j]] = Math.max(near[visit[i][j]], area.get(visit[ny][nx]));
					}
				}
			}
			
			int maxArea1 = 0, maxArea2 = 0;
			for (int i = 1; i <= idx; ++i) {
				maxArea1 = Math.max(maxArea1, area.get(i));
				maxArea2 = Math.max(maxArea2, area.get(i) + near[i]);
			}
			bw.write(idx + "\n" + maxArea1 + "\n" + maxArea2 + "\n");
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
	
	public static void dfs(int y, int x) {
		cnt++;
		visit[y][x] = idx;
		for (int d = 0; d < 4; ++d) {
			if (((map[y][x] >> d) & 1) == 1) continue;
			int ny = y + dir[d][0];
			int nx = x + dir[d][1];
			if (ny < 0 || nx < 0 || ny >= m || nx >= n) continue;
			if (visit[ny][nx] != 0) continue;
			dfs(ny, nx);
		}
	}
}