[백준] 2468번. 안전 영역(JAVA)

문제

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

---

풀이(22분)

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

public class Main {

    static int n, count, answer;
    static int[][] map;
    static boolean[][] visited;
    static Queue<Point> queue = new LinkedList<>();
    static int[] dx = new int[]{0,0,-1,1};
    static int[] dy = new int[]{-1,1,0,0};

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

        n = Integer.parseInt(br.readLine());
        map = new int[n][n];
        visited = new boolean[n][n];
        int maxHeight = 0;
        int minHeight = 101;
        for(int i = 0; i < n; i++){
            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]);
                minHeight = Math.min(minHeight, map[i][j]);
            }
        }

        answer = 1; // 모든 영역이 안 잠겼을 때 최솟값 1
        
        for(int i = minHeight; i < maxHeight; i++){ // 최소 높이 ~ 최대 높이
            count = 0;
            for(int j = 0; j < n; j++){
                for(int k = 0; k < n; k++){
                    if(map[j][k] <= i){
                        visited[j][k] = true; // 물에 잠김
                    }else{
                        visited[j][k] = false; // 물에 안 잠김
                    }
                }
            }
            for(int j = 0; j < n; j++){
                for(int k = 0; k < n; k++){
                    if(!visited[j][k]){ // bfs
                        queue.add(new Point(j, k));
                        visited[j][k] = true;
                        count++;
                        bfs();
                    }
                }
            }
            
            answer = Math.max(answer, count);
        }

        System.out.println(answer);
    }

    static void bfs(){
        while(!queue.isEmpty()){
            Point cur = queue.poll();
            for(int i = 0; i < 4; i++){
                int nextRow = cur.row + dx[i];
                int nextCol = cur.col + dy[i];
                // 범위 안에 있고, 체크된 적이 없다면
                if(isInBounds(nextRow, nextCol) && !visited[nextRow][nextCol]){
                    queue.add(new Point(nextRow, nextCol));
                    visited[nextRow][nextCol] = true;
                }
            }
        }
    }

    static boolean isInBounds(int row, int col){
        return row >= 0 && row < n && col >= 0 && col < n;
    }

    static class Point{
        int row, col;

        public Point(int row, int col){
            this.row = row;
            this.col = col;
        }
    }
}

---

문제 풀이 전략

 

모든 높이에 대해 bfs를 하면 안 될까?라는 생각이 처음부터 들었다.

가장 단순한 풀이이기도 하고, 해답일 것 같았다.

그래도 코드를 작성하기 전 시간 초과에 대한 고려를 하지 않을 수 없었고, 계산해 보았다.

 

1. n <= 100

2. 높이 <= 100

 

즉, 두 개의 기준을 보았을 때 좌표평면은 100 * 100이고, 높이 또한 100이므로 최대 100^3의 계산을 해야 한다.

결과적으로 1,000,000의 계산만 해주면 된다는 것을 알았고 bfs로 해결하였다.