백준[JAVA] 2468번 안전 영역

 

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

2468번: 안전 영역

-문제-

-입력-

첫째 줄에는 어떤 지역을 나타내는 2차원 배열의 행과 열의 개수를 나타내는 수 N이 입력된다. N은 2 이상 100 이하의 정수이다. 둘째 줄부터 N개의 각 줄에는 2차원 배열의 첫 번째 행부터 N번째 행까지 순서대로 한 행씩 높이 정보가 입력된다. 각 줄에는 각 행의 첫 번째 열부터 N번째 열까지 N개의 높이 정보를 나타내는 자연수가 빈 칸을 사이에 두고 입력된다. 높이는 1이상 100 이하의 정수이다.

-출력-

첫째 줄에 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 출력한다.

 

-------------------------------------------------------------------------------------------------------------------------------------

bfs로 독립된 부분을 세어주면 되는 문제다. 하지만 기준이 되는 높이를 어떻게 효율적으로 설정하면 될까 고민하다가 자료구조 Set을 이용하였다.

Set은 중복된 원소가 삽입될 수 없기때문에 입력으로 주어지는 값을 Set에 삽입해주고 마지막으로 문제에서 주어진 0까지 삽입해주었다.

Set덕분에 문제에서 필요한 만큼만 bfs를 진행할 수 있어 시간이 줄어들었다.

그 후 이중 반복문을 통해 기준에 부합하는 것들은 큐에 넣어서 bfs를 진행하였다.

import java.util.*;
import java.lang.*;
import java.io.*;
import java.awt.*;
class Solving {
    static int N;//사이즈
    static int answer;//답
    static int count;//각각 기준에 따른 값
    static int[][] pan;//2차원 배열
    static boolean[][] isChecked;//방문여부
    static Queue<Point> q=new LinkedList<>();//bfs를 위한 큐 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        HashSet<Integer> set = new HashSet<>();//물의 높이를 담을 Set
        N = Integer.parseInt(br.readLine());
        answer=Integer.MIN_VALUE;
        count=0;
        pan = new int[N][N];
        isChecked = new boolean[N][N];
        answer=Integer.MIN_VALUE;
        for(int i=0;i<N;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0;j<N;j++){
                pan[i][j]=Integer.parseInt(st.nextToken());
                set.add(pan[i][j]);//set에 값 삽입(중복된 값은 삽입X)
            }
        }
        set.add(0);//0의 케이스까지 생각해야하므로 0 삽입
        Iterator<Integer> itr = set.iterator();
        while(itr.hasNext()){//set은 순서가 없으므로 이터레이터를 통한 탐색
            int standard= itr.next();//기준이 될 물의 높이 
            for(int i=0;i<N;i++){
                for(int j=0;j<N;j++){
                    if(pan[i][j]<=standard||isChecked[i][j]){
                        continue;//물에 잠겨있거나 이미 방문한 곳이면 다음으로 넘어감
                    }
                    count++;//독립된 곳이라 판단하여 카운트++;
                    q.add(new Point(i,j));
                    while(!q.isEmpty()){
                        int qsize= q.size();
                        for(int a=0;a<qsize;a++){
                        Point p=q.poll();
                        int x=p.x;
                        int y=p.y;
                            if(isRange(x-1,y)&&!isChecked[x-1][y]&&pan[x-1][y]>standard){//안 잠겨있거나 2차원배열 범위내에 있거나 미방문상태면 큐에 추가
                                isChecked[x-1][y]=true;
                                q.add(new Point(x - 1, y));
                            }
 
                            if(isRange(x+1,y)&&!isChecked[x+1][y]&&pan[x+1][y]>standard){
                                isChecked[x+1][y]=true;
                                q.add(new Point(x + 1, y));
 
                            }
 
                            if(isRange(x,y+1)&&!isChecked[x][y+1]&&pan[x][y+1]>standard){
                                isChecked[x][y+1]=true;
                                q.add(new Point(x , y+1));
                            }
 
                            if(isRange(x,y-1)&&!isChecked[x][y-1]&&pan[x][y-1]>standard){
                                isChecked[x][y-1]=true;
                                q.add(new Point(x , y-1));
                            }
                        }
 
                    }
                }}
            if(answer<count){//전에 있던 answer보다 값이 클시 값 변경
                answer=count;
            }
            for(int index=0;index<N;index++){
                Arrays.fill(isChecked[index],false);//새로운 기준에 이용하기위한 방문여부 
            }
            count=0;
 
 
            }
        System.out.println(answer);
 
 
        }
        
public static boolean isRange(int x,int y){
        return x>=0&&x<N&&y>=0&&y<N;
}
}