BOJ 2468 안전영역

문제 분석

- BOJ_2667_단지번호붙이기 와 비슷하면서도 쉬운 문제라고 생각했다. 

- 비가 오는 양마다 bfs로 안전영역을 탐색하고, 각 영역 탐색 후 최대 개수를 비교하면 된다.

 

 

문제 풀이

1) 비가 오는 범위를 0에서 가장 높은 지역의 높이까지 계산하여 각각 bfs를 계산한다.

2) bfs탐색을 통해 안전 영역을 계산한다.

3) 각각의 안전영역을 비교하여 출력한다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int N, rain, max, ans, tmp;
	static boolean[][] visited;
	static int[][] map;
	private static int[] dr = { -1, 1, 0, 0 }; // 좌우상하
	private static int[] dc = { 0, 0, -1, 1 };

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		map = new int[N][N];
		visited = new boolean[N][N];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				int num = Integer.parseInt(st.nextToken());
				map[i][j] = num;
				max = num > max ? num : max;
			}
		}
		for (int r = 0; r <= max; r++) {// 비의 양이 0부터 max까지
			tmp = 0;
			visited = new boolean[N][N];
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (map[i][j] > r && !visited[i][j]) {
						tmp++;
						bfs(r, i, j);
					}
				}
			}
			ans = Math.max(ans, tmp);
		} // 비의 양에 따른 for문

		System.out.println(ans);

	}// main

	static void bfs(int r, int x, int y) {

		Queue<Point> q = new LinkedList<>();

		q.add(new Point(x, y));
		visited[x][y] = true;

		while (!q.isEmpty()) {
			Point cur = q.poll();
			int curX = cur.x;
			int curY = cur.y;

			for (int d = 0; d < 4; d++) { // 상하좌우
				int nx = curX + dr[d];
				int ny = curY + dc[d];
				if (nx >= 0 && ny >= 0 && nx < N && ny < N) {
					if (map[nx][ny] > r && !visited[nx][ny]) {
						q.add(new Point(nx, ny));
						visited[nx][ny] = true;

					}
				}
			}
		}

	}// bfs

	static class Point {
		int x, y;

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

	}// Point
}// class-end