BOJ_안전영역_2468

1. 과정

- 아무 지역도 잠기지 않을 경우가 있으므로 answer는 1부터 시작한다.

- 빗물의 높이는 1부터 시작해 가장 높은 지역의 높이까지 반복하면 된다.

- 상하좌우 bfs를 돌면서 visit체크를 해주며 몇개의 안전 영역이 있는지 체크해주면 된다.

 

 

2. 구현

언어 : JAVA

메모리 : 64,612 kb

시간 : 480 ms

import java.util.*;

public class Main {
	static int N, max, answer;
	static int[][] map;
	static boolean[][] visit;
	static int[] dr = { -1, 1, 0, 0 };
	static int[] dc = { 0, 0, -1, 1 };

	static class Pair {
		int r, c;

		public Pair(int r, int c) {
			this.r = r;
			this.c = c;
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		map = new int[N][N];
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				map[i][j] = sc.nextInt();
				max = Math.max(max, map[i][j]);
			}
		}
		answer = 1;
		for (int i = 1; i <= max; ++i) {
			rain();	//매번 빗물의 높이를 1씩 높여줌
			solve();	//안전영역 구하는 메소드
		}
		System.out.println(answer);
	}

	private static void solve() {
		int cnt = 0;
		visit = new boolean[N][N];
		Queue<Pair> q = new LinkedList<>();
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				if (visit[i][j] || map[i][j]<=0)
					continue;
				visit[i][j] = true;
				q.add(new Pair(i, j));
				while(!q.isEmpty()) {
					Pair p = q.poll();
					int r = p.r;
					int c = p.c;
					int tr, tc;
					for(int k=0; k<4; ++k) {
						tr = r+dr[k];
						tc = c+dc[k];
						if(tr<0 || tc<0 || tr>=N || tc>=N || visit[tr][tc] || map[tr][tc]<=0) continue;
						visit[tr][tc] = true;
						q.add(new Pair(tr, tc));
					}
				}
				cnt++;
			}
		}
		answer = Math.max(answer, cnt);
	}

	private static void rain() {
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				map[i][j] -= 1;
			}
		}
	}

}