BOJ - 2234 ) 성곽

 

---

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

2234번: 성곽

 

---

주어진 맵에서 성곽의 크기를 구하면서 벽하나를 제거해서 합친 면적중 가장 큰 값을 찾는 문제이다.

 

성곽의 크기를 구할때 이미 각 면적의 합을 구하고 인접여부만 CHECK배열로 확인해 준다음

 

인접해있다면, 두 면적을 합친값 중 가장 큰 값을 답으로 선택한다.

 

다음 BFS진행시에 비트연산을 해주어야하는 신박한 문제 :)

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.StringTokenizer;

public class 성곽 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int map[][] = new int[m][n];
		int 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());
			}
		}
		
		int maxarea = -1 ; int mark = 0;
		int dir[][] = {{1,0},{-1,0},{0,-1},{0,1}};
		ArrayDeque<int []> dq = new ArrayDeque<>(); // 0 1 coordi 2 area
		for(int i = 0 ; i < m ; i++) {
			for(int j= 0 ; j < n ; j++) {
				if(visit[i][j] ==0) {
					mark++;
					visit[i][j] = mark;
					dq.add(new int[] {i,j});
					while(!dq.isEmpty()) {
						int [] now = dq.poll();
						for(int k = 0 ; k < 4 ; k++) {
							int ny = now[0] + dir[k][0];
							int nx = now[1] + dir[k][1];
							if(ny >=0 && nx >=0 && ny < m && nx <n) {
								if(k==0 && ((map[ny][nx] & 2) !=2) && ((map[now[0]][now[1]] & 8) != 8) && visit[ny][nx]==0){
									visit[ny][nx] = mark;
									dq.add(new int[] {ny,nx}); //내가 남쪽 가려는방향 북쪽
								} else if(k==1 && ((map[ny][nx] & 8) !=8) && ((map[now[0]][now[1]] & 2) != 2) && visit[ny][nx]==0) {
									visit[ny][nx] = mark;
									dq.add(new int[] {ny,nx}); // 내가 북쪽 가려는방향 남쪽
								} else if(k==2 && ((map[ny][nx] & 4) !=4) && ((map[now[0]][now[1]] & 1) != 1) && visit[ny][nx]==0) {
									visit[ny][nx] = mark;
									dq.add(new int[] {ny,nx});
								} else if(k==3 && ((map[ny][nx] & 1) !=1) && ((map[now[0]][now[1]] & 4) != 4) && visit[ny][nx]==0) {
									visit[ny][nx] = mark;
									dq.add(new int[] {ny,nx});
								}
							}
						}
					}
				}
			}
		}
		int cnt[] = new int[mark];
		boolean check[][] = new boolean[mark][mark];
		for(int i = 0 ; i < m; i++) {
			for(int j = 0 ; j < n ; j++) {
				cnt[visit[i][j]-1]++;
				if( maxarea < cnt[visit[i][j]-1]) {
					maxarea = cnt[visit[i][j]-1];
				}
				for(int k = 0 ;k < 4 ; k++) {
					int ny = i + dir[k][0];
					int nx = j + dir[k][1];
					if(ny >=0 && nx >=0 && ny < m && nx <n) {
						if(visit[i][j] != visit[ny][nx] && !check[visit[i][j]-1][visit[ny][nx]-1]) {
							check[visit[i][j]-1][visit[ny][nx]-1] = true;
						}
					}
				}
			}
		}
		int removearea=-1;
		for(int i = 0 ; i < mark ; i++) {
			for(int j = 0 ; j < mark ;  j++) {
				if(check[i][j]) {
					int temp = cnt[i] + cnt[j];
					if( removearea < temp) {
						removearea = temp;
					}
				}
			}
		}
		sb.append(mark +"\n"+maxarea +"\n"+removearea);
		System.out.println(sb);
	}
	
}

---