[백준 자바 2468] 안전 영역 (실버1)

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

2468번: 안전 영역

BFS로 풀었다. 정답 비율 보고 겁먹었는데 생각보다 할만한 난이도. 원트클! 

 

대강의 흐름을 이렇게 잡았다. 

1. BFS로 물에 안 잡기는 영역을 세기

2. (비가 안 내릴 수 있으니) 0부터 물에 다 잡기는 최대 높이까지 +1씩 반복문으로 돌면서 최대 영역 개수 구하기 

 

우선 String을 int 로 변환해주는 stoi 함수는 편의상 만들어 두고 쓰는 함수이다. 

 

그리고 지역의 행, 열 길이인 N

지역의 최대 높이인 max, 

안전 영역을 저장할 res, 

지역의 높이 지도를 저장할 map 변수를 쓴다. 

 

이후로 입력에 따라 맵을 채워주는데 

 

최대 높이는 따로 구해준다. 

 

 

 

 

 

 

 

그 다음, 비가 안 내리는 경우인 0부터~비가 너무 내려서 전부 물에 잠겨버리는 최대 높이 max 까지 1씩 올라가면서 BFS를 돌려주고, BFS가 실행이 될 때마다 안전 영역이 1개씩 발견이 된다는 뜻이므로 cnt도 +1 해준다. 

 

 

그다음으로 상하좌우 탐색을 위해 dx, dy를 선언,

 

전형적인 bfs 코드를 작성해준다. 

 

다만 마지막 if문에서는 범위와 방문 여부 체크 말고도 안전 영역 체크를 위해 height 보다 큰 경우에 큐에 넣어준다. 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

전체 코드 

package p2468;

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

public class Main {
    static int stoi(String s) { // String to int
        return Integer.parseInt(s);
    }

    static int N, max = Integer.MIN_VALUE, res = 0;
    static int[][] map;

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

        N = stoi(st.nextToken()); // 한 변의 길이를 받아와서
        map = new int[N][N]; // 지도 배열을 만들어주기.

        for (int i = 0; i < N; i++) { // 맵 채우기
            st = new StringTokenizer(br.readLine(), " ");

            for (int j = 0; j < N; j++) {
                int x = stoi(st.nextToken());
                map[i][j] = x;
                max = Math.max(max, x); // 최대 높이를 따로 저장
            }
        }

        int height = 0; // 현재 높이
        while (height <= max) { // 0부터 최대 높이까지 1씩 올라가면서 안전 영역 측정
            boolean[][] visited = new boolean[N][N];
            int cnt = 0; // 안전 영역 저장용
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (!visited[i][j] && map[i][j] > height) { // 방문 안 했고 현재 높이보다 높으면 (안전영역이면)
                        cnt++; // 안전 영역을 발견했으니 +1 해주고
                        bfs(i, j, height, visited); // bfs로 돌면서 인접한 영역을 하나로 퉁치기
                    }
                }
            }
            res = Math.max(res, cnt); // 최대 안전 영역을 저장
            height++; // 강수량 높이 올리기
        }

        System.out.println(res);
    }

    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static void bfs(int n, int m, int height, boolean[][] visited) {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{n, m});
        visited[n][m] = true;

        while (!q.isEmpty()) {
            int[] pos = q.poll();
            int x = pos[0]; // 현재 x
            int y = pos[1]; // 현재 y

            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i]; // 인접 x
                int ny = y + dy[i]; // 인접 y
                if (0 <= nx && nx < N && 0 <= ny && ny < N && !visited[nx][ny] && map[nx][ny] > height) {
                    visited[nx][ny] = true;
                    q.add(new int[]{nx, ny});
                }
            }
        }
    }
}