[BJ2469] 안전 영역

 백준 - 안전영역 

문제 링크

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

2468번: 안전 영역

 

문제 입출력

5
6 8 2 6 2
3 2 3 4 6
6 7 3 3 2
7 2 5 3 6
8 9 5 2 7

5

7
9 9 9 9 9 9 9
9 2 1 2 1 2 9
9 1 8 7 8 1 9
9 2 7 9 7 2 9
9 1 8 7 8 1 9
9 2 1 2 1 2 9
9 9 9 9 9 9 9

6

2
1 1
1 1

1

 

문제 풀이

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


public class Main {
	static int ans, N;
	static int[][] map, mapTemp;
	static boolean[][] visit;

	// 상하좌우
	static int[] dy = { -1, 1, 0, 0 };
	static int[] dx = { 0, 0, -1, 1 };


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

		N = Integer.parseInt(br.readLine());
		map = new int[N][N];
		mapTemp = new int[N][N];
		int maxN = Integer.MIN_VALUE;
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				int m = Integer.parseInt(st.nextToken());
				mapTemp[i][j] = m;
				maxN = Math.max(maxN, m);
			}

		}

		// 초기화
		ans = 0;

		// 탐색
		for (int i = 0; i <= maxN; i++) {
			// 맵 초기화
			int max = 0;
			copyMap();

			visit = new boolean[N][N];

			check(i);

			for (int y = 0; y < N; y++) {
				for (int x = 0; x < N; x++) {
					if (map[y][x] == -1) continue;
					if (visit[y][x]) continue;

					dfs(y, x);
					max++;
				}

			}

			ans = Math.max(ans, max);

		}

		// 출력
		System.out.println(ans);

	} // end main


	private static void dfs(int y, int x) {
		visit[y][x] = true;

		for (int d = 0; d < 4; d++) {
			int ny = y + dy[d];
			int nx = x + dx[d];

			if (ny < 0 || ny >= N || nx < 0 || nx >= N) continue;
			if (visit[ny][nx]) continue;
			if (map[ny][nx] == -1) continue; // 물에 잠겼으면

			dfs(ny, nx);
		}

	} // end bfs


	private static void copyMap() {
		for (int i = 0; i < N; i++) map[i] = mapTemp[i].clone();

	} // end copyMap


	private static void check(int n) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) if (map[i][j] <= n) map[i][j] = -1; // 잠긴 곳 체크
		}

	} // end check
}

• dfs를 이용하여 풀 수 있습니다.
• 0부터 제일 최대의 물 높이 까지 돌아야 합니다.
  • 0부터 돌아야하는 이유는 물이 잠기지 않는 경우도 있기 때문입니다.
• 물 높이마다 돌 때 적절한 초기화를 해줘야합니다.

 

 

 

 

 

 

 

 

 

# 백준 안전영역 반례 # 백준 안전영역 java # 백준 안전영역 dfs

---