99클럽 코테 스터디 4일차 TIL - 안전영역 (백준 2468번)

오늘의 학습 키워드

- DFS

- BFS

- Flood Fil

- 완전 탐색

- 안전 영역

---

공부한 내용 정리

오늘은 2차원 지도에서 비가 내릴 때, 특정 높이 이하의 지역이 물에 잠기는 상황을 가정하고, 잠기지 않은 안전한 지역의 개수를 세는 문제를 풀었다.

높이 1부터 최대 높이까지 반복하면서, DFS로 침수되지 않은 영역을 탐색했다.

각 높이에 대해 안전한 영역의 개수를 세어 그 중 최대값을 구하는 방식이다.

 

문제 해결 전략은 다음과 같다:

1. 비의 높이를 0부터 최대 높이까지 올려가며 반복

2. 각 높이마다 물에 잠기지 않은 영역을 DFS로 탐색

3. 탐색된 영역 수를 카운트하고, 그 중 최대값 저장

---

소스코드

import java.util.*;

public class Main {
    static int N; // 지역의 크기
    static int[][] map; // 지역의 높이 정보
    static boolean[][] visited; // 방문 여부 체크용 배열
    static int[] dx = {0, 0, 1, -1}; // 상하좌우 이동을 위한 x축 변화
    static int[] dy = {1, -1, 0, 0}; // 상하좌우 이동을 위한 y축 변화

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt(); // 지역 크기 입력
        map = new int[N][N];

        int maxHeight = 0; // 지역 내 가장 높은 높이 저장용
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                map[i][j] = sc.nextInt(); // 높이 정보 입력
                maxHeight = Math.max(maxHeight, map[i][j]); // 최고 높이 갱신
            }
        }

        int maxSafeZone = 0; // 안전 영역의 최대 개수

        // 모든 높이(강수량)에 대해 시뮬레이션 수행
        for (int h = 0; h <= maxHeight; h++) {
            visited = new boolean[N][N]; // 매 시뮬레이션마다 방문 초기화
            int count = 0; // 현재 높이에서의 안전 영역 개수

            // 2차원 배열 전체 순회
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    // 방문하지 않았고, 현재 높이보다 높은 곳만 탐색
                    if (!visited[i][j] && map[i][j] > h) {
                        dfs(i, j, h); // DFS 탐색 시작
                        count++; // 안전 영역 하나 발견
                    }
                }
            }

            // 현재 높이에서의 안전 영역 수가 최대라면 갱신
            maxSafeZone = Math.max(maxSafeZone, count);
        }

        System.out.println(maxSafeZone); // 결과 출력
    }

    // DFS 함수: 상하좌우로 연결된 모든 안전 지점 방문
    static void dfs(int x, int y, int h) {
        visited[x][y] = true; // 현재 지점 방문 처리

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

            // 범위를 벗어나지 않고, 방문하지 않았고, 높이가 물에 잠기지 않은 경우
            if (nx >= 0 && nx < N && ny >= 0 && ny < N) {
                if (!visited[nx][ny] && map[nx][ny] > h) {
                    dfs(nx, ny, h); // 다음 지점 DFS 호출
                }
            }
        }
    }
}

---

오늘의 회고

• 어떤 문제가 있었고, 나는 어떤 시도를 했는지

처음에는 안전 영역을 단일 높이에 대해서만 구하려고 했는데, 모든 높이에 대해 구해야 한다는 것을 늦게 파악했다.

 

• 어떻게 해결했는지

최대 높이까지의 모든 높이에 대해 반복문을 돌리며 DFS를 적용해 문제를 해결했다.

 

• 무엇을 새롭게 알았는지

한 번의 DFS 탐색이 하나의 연결된 안전 영역을 의미하고, 이를 반복하며 안전 영역의 개수를 셀 수 있다는 점.

 

• 내일 학습할 것은 무엇인지

BFS로도 같은 문제를 해결해보고, DFS/BFS를 스스로 구현 연습해볼 계획.

---