[백준] 2468번: 안전 영역

 

문제 파악

- 친구의 친구까지만 구하기

 

<알고리즘 분류>
-완전 탐색

 

접근 방법

-안전 영역이 '최대'가 되는 경우를 구해내기

-단순 주어진 강수량 이하를 기준으로 dfs(완전탐색)하는 문제가 아님

-모든 강수량의 case를 탐색해야 함

    -탐색 범위는 지역 최대 높이까지(강수량 최대 case)

 

 

 

코드 구현

package org.server;
import java.io.*;
import java.util.*;

public class Main {
    static boolean[][] visited;
    static int[][] ground;
    static int N;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        ground = new int[N][N];
        StringTokenizer st;
        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());
                ground[i][j]=height;
                maxHeight = Math.max(maxHeight, height);
            }
        }
        int maxGround = 0;
        for(int z=0;z<=maxHeight;z++){//비가 아예 안올 경우도 고려
            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]&&ground[i][j]>z){
                        dfs(i,j,z);
                        cnt++;
                    }
                }
            }
            maxGround = Math.max(maxGround,cnt);
        }
        
        System.out.println(maxGround);

    }
    public static void dfs(int x,int y,int height){
        visited[x][y]=true;
        int[] toX = {1,-1,0,0};
        int[] toY = {0,0,1,-1};

        for(int i=0;i<4;i++){
            int rx = x+toX[i];
            int ry = y+toY[i];
            if(rx>=0&&rx<N&&ry>=0&&ry<N&&!visited[rx][ry]&&ground[rx][ry]>height){
                //System.out.println(ground[rx][ry]+"는 "+N+"이하");
                dfs(rx, ry,height);
            }
        }
    }
}

 

배우게 된 점

-문제를 잘 파악하자. 강수량이 주어지지 않았으니, -> 문제를 다시 읽고 요구 조건을 명확히 파악하는 게 중요함

-완전 탐색이라고 생각했으나 아니었음.