백준 2468번: 안전 영역

핵심

• 안전 영역을 구하기 위해 BFS 탐색
• 비의 높이 = k 라고 가정할 때, 높이 > k인 지역들로만 BFS 탐색
• 높이 기준을 0 ~ maxHeight까지 변경하면서 최대 안전 영역 개수를 갱신

---

실수 주의 포인트

비가 아예 안 오는 경우, 즉 k = 0도 반드시 고려해야 합니다.
이걸 누락하면 테스트케이스는 통과해도 실제 채점에서 오답 날 수 있어요.

 

import java.io.*;
import java.util.*;

public class Main {
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int[][] map;
    static boolean[][] visited;
    static int N;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];

        int maxHeight = 0;

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

        int result = 0;
        for (int h = 0; h <= maxHeight; h++) {
            visited = new boolean[N][N];
            int count = 0;

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (!visited[i][j] && map[i][j] > h) {
                        bfs(i, j, h);
                        count++;
                    }
                }
            }
            result = Math.max(result, count);
        }

        System.out.println(result);
    }

    static void bfs(int x, int y, int height) {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{x, y});
        visited[x][y] = true;

        while (!q.isEmpty()) {
            int[] now = q.poll();
            int cx = now[0];
            int cy = now[1];

            for (int i = 0; i < 4; i++) {
                int nx = cx + dx[i];
                int ny = cy + dy[i];

                if (nx >= 0 && ny >= 0 && nx < N && ny < N) {
                    if (!visited[nx][ny] && map[nx][ny] > height) {
                        visited[nx][ny] = true;
                        q.add(new int[]{nx, ny});
                    }
                }
            }
        }
    }
}

 

항목	내용
알고리즘	BFS
핵심 로직	높이별로 안전 영역 BFS 탐색
시간복잡도	O(N*N*H) (H는 최대 높이 100까지)
실수 방지	비가 안 오는 상황 (height=0)도 꼭 포함!

 

[ 시간복잡도 ]

전체 반복 구조

1. **높이(h)**를 1부터 maxHeight까지 순회 → 최대 100번
2. 각 **높이(h)**마다 모든 좌표를 순회하면서 방문하지 않은 안전 영역 찾기:
   • 좌표 수: N x N → 최대 10,000
   • 각 좌표마다 DFS (or BFS) 호출: 한 영역당 O(N²) 내에서 한 번씩만 탐색함

DFS or BFS 내 연산

• DFS/BFS는 각 좌표를 최대 한 번씩만 방문하므로, 한 높이 당 O(N²)

결과

 

• 시간복잡도: O(N² × H) (N ≤ 100, H ≤ 100)
• 최대 연산 횟수: 약 1,000,000회 → 1초 시간 제한 안에 통과 가능