[백준] 2648번 : 안전 영역

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

 

 

 

 

문제 파악

-특정 강수량마다 잠기는 곳/안 잠기는 곳 구분하여 배열 저장

- 안잠기는 곳을 '섬'이라 칭하자

- dfs원리로 매 케이스의 섬을 카운트하여 가장 큰 카운트를 리턴

 

🎈[알고리즘 분류]

• 그래프 이론
• 브루트포스 알고리즘
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

 

접근 방법

-BufferedReader와 StringTokenizer 이용해 값을 입력받기

- BufferedReader는 처음에 선언하고 br.readLine()으로 받기

- StringTokenizer는 한 줄단위로 쪼갤 때마다 선언..!, delimeter는 뒤에 적어주기, 실제 쪼갤 때는 st.nextToken() 사용

-각 강수량마다 잠기는 지역/안잠기는 지역 비교문으로 false/true 체크해주기

-> 이어서 해당 그래프에서 false인 부분(안잠긴 부분, 섬) 만나면 dfs 돌아서 섬 하나 순회 다 돌고오면 카운트해주기

 -> 그렇게 섬 갯수를 카운트해주고,

-> max카운트 값을 갱신해간다.

-강수량 중, 가장 max카운트를 계산해 리턴하기

 

코드 구현

package com.baekjoon;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class p2468_안전영역 {
    public static int 안전영역() throws IOException {
        //그래프 입력받기 + 최대 높이 찾기(max잠김)
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(br.readLine());
        int[][] graph = new int[n][n];
        int max_height=0;
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine()," ");
            for (int j = 0; j < n; j++) {
                graph[i][j] = Integer.parseInt(st.nextToken());
                if(max_height<graph[i][j]){
                    max_height=graph[i][j];
                }
            }
        }

        //System.out.println(Arrays.deepToString(graph));
        int max_cnt=0;//답이 될 최대 카운트
        for(int k=0;k<max_height;k++) {//강수량마다 잠기는 부분 체크
            boolean[][] down = new boolean[n][n];//false로 매번 초기화
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (k >= graph[i][j]) {
                        down[i][j] = true;//강수량k에따라 잠기는 부분들
                    }
                }
            }
            //count하기
            int cnt=0; //초기화되어야함
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if(!down[i][j]){
                        dfs(i,j,n,down);
                        cnt++;
                    }
                }
            }
            if(max_cnt<cnt){
                max_cnt=cnt;
            }

        }
        return max_cnt;
    }

    public static void dfs(int i, int j, int n, boolean[][] down) {
        int[] toX = {-1,1,0,0};
        int[] toY = {0,0,-1,1};
        down[i][j]=true;
        for(int k=0;k<4;k++){
            int x=i+toX[k];
            int y=j+toY[k];
            if(x>=0&&y>=0&&x<n&&y<n&&!down[x][y]){
                dfs(x,y,n,down);
            }
        }
    }

    public static void main(String[] args) throws IOException {
        //p2468_안전영역 ay = new p2468_안전영역();
        int answer = 안전영역();
        System.out.println(answer);
    }


}

 

배우게 된 점

-dfs를 완전히 타파하기 위해 푼 응용 문제

그렇게까지 어렵지 않은 문제였다.

 

 

끝