[Baekjoon] 2468 - 안전 영역

📝 문제

 

 

🔑 풀이 과정

· 이 문제도 앞서 풀어본 문제들과 같이 기본적으로 연결요소의 개수를 구하는 것이다. 그러나 지금까지는 연결요소의 개수를 한 번만 구했다면, 이 문제는 비의 양에 따른 모든경우에서의 연결 요소의 개수를 구하고, 그 중에서 최대인 것을 찾는 것이다.

 

· 그래서 각 경우의 연결요소 개수를 세는 count 변수를 두고, max라는 변수를 둬서 연결요소의 최댓값을 저장하고, 탐색이 이 다 끝난뒤 출력한다.

 

· 각 경우마다 탐색을 하기 전에 방문배열을 초기화 시켜줘야 한다.

 

· BFS 메서드의 인자에 시작점의 x, y 좌표 뿐 아니라 어느 높이까지 잠기는지에 대한 인자도 넣어주었다. 인자가 h라면 높이가 h이하인 지점이 잠김 → h 초과인 범위를 탐색하면 된다.

 

· 높이가 1이상 100이하의 정수로, 매우 범위가 작기때문에 탐색 범위를 0부터 99까지만 해도 시간은 괜찮을 것 같았다. 그래도 탐색범위를 최대한 줄이고자 입력받을 때 가장 낮은 높이, 가장 높은 높이를 구해주었다. 그리고 탐색 범위를 (가장 낮은 높이 - 1 ) ~ (가장 높은 높이 - 1)로 설정했다.

 

· 왜 가장 낮은 높이 -1, 가장 높은 높이 -1 이냐면

문제의 아래의 노트에 "아무 지역도 물에 잠기지 않을 수도 있다" 라는 조건이 있기 때문에 가장 낮은 높이 -1부터 해주어야 한다. (가장 낮은 높이 부터 해주면 가장 낮은 지점은 무조건 잠김)

또 가장 높은 높이를 기준으로 탐색하면 그때는 모든 지점이 물에 잠기기 때문에 안전영역의 개수가 무조건 0이다.

[예시]

 

 

🔓 답안

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static int[] dx = {-1, 0, 0, 1};
    static int[] dy = {0, -1, 1, 0};

    static int N;

    static int[][] arr;
    static boolean[][] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        //입력
        N = Integer.parseInt(br.readLine());

        arr = new int[N][N];
        visited = new boolean[N][N];

        int minHeight = 101; //지역 내에서 가장 낮은 높이
        int maxHeight = 0; //지역 내에서 가장 높은 높이
        for(int i = 0; i < N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < N; j++){
                int height = Integer.parseInt(st.nextToken());
                arr[i][j] = height;

                if(height < minHeight)
                    minHeight = height;

                if(height > maxHeight)
                    maxHeight = height;
            }
        }
        //입력 종료

        //BFS수행
        //높이가 i이하인 지점을 모두 잠기게 하는 비가 내린다.
        int max = 0;
        for(int i = minHeight - 1; i <= maxHeight - 1; i++){

            //방문배열 초기화
            initVisit();

            int count = 0; //연결 요소의 개수 count하는 변수
            for(int j = 0; j < N; j++){
                for(int k = 0; k < N; k++){
                    if((arr[j][k] > i) && (!visited[j][k])){
                        count++;
                        BFS(j, k, i);
                    }
                }
            }

            if(count > max)
                max = count;
        }

        //출력
        bw.write(max + "\n");
        bw.flush();
        bw.close();
    }

    //BFS 메서드
    static void BFS(int x, int y, int h){
        Queue<int[]> queue = new LinkedList<>();
        visited[x][y] = true;
        queue.add(new int[] {x, y});

        while(!queue.isEmpty()){
            int[] now = queue.remove();

            for(int i = 0; i < 4; i++){
                int newX = now[0] + dx[i];
                int newY = now[1] + dy[i];

                if((newX >= 0) && (newX < N) && (newY >= 0) && (newY < N)){
                    if((arr[newX][newY] > h) && (!visited[newX][newY])){
                        visited[newX][newY] = true;
                        queue.add(new int[] {newX, newY});
                    }
                }
            }
        }

    }

    //방문 배열 초기화 메서드
    static void initVisit(){
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                visited[i][j] = false;
            }
        }
    }

}

 

 

 

🖤 알고리즘 분류

- 그래프 이론

- 브루트포스 알고리즘

- 그래프 탐색

- 너비 우선 탐색

- 깊이 우선 탐색