[백준] 알고리즘 분류(브루트 포스,JAVA)2468번, 안전 영역

문제 링크

2468번: 안전 영역

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. N의 크기의 2차원 배열에는 각 지역의 높이 정보가 저장됩니다.

2. 비의 양에 따라 지역이 잠기지 않는 구역을 안전 구역이라고 한다.

3. 안전 구역은 인접한 안전 구역도 같은 범위에 포함시킨다.

4. 안전 구역의 크기는 안전 구역의 개수를 뜻한다.

5. 비의 양을 조절할 수 있을 때 안전 구역의 최대 개수를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 올 수 있는 비의 양의 모든 경우에 대하여 BFS탐색을 이용하여 안전 구역의 개수를 구합니다.

 

3. 안전 구역의 최대 개수를 결과로 출력합니다.

 

올 수 있는 비의 양.

 

비의 양은 각 지역의 높이만큼 올 수 있습니다.

 

2 4

4 5

 

지역이 존재할 때 올 수 있는 비의 양은

2, 4, 5입니다.

 

2보다 작은 값의 높이 :  아무 지역도 물에 잠기지 않는다.

비의 양 3 :  2와 동일한 지역만 물에 잠긴다.

 

 

예제입력 2.

 

1. 입력된 정보를 저장합니다.

 

N : 7

 

9	9	9	9	9	9	9
9	2	1	2	1	2	9
9	1	8	7	8	1	9
9	2	7	9	7	2	9
9	1	8	7	8	1	9
9	2	1	2	1	2	9
9	9	9	9	9	9	9

 

2. 올 수 있는 비의 양의 모든 경우에 대하여 BFS탐색을 이용하여 안전 구역의 개수를 구합니다.

 

올 수 있는 비의 양.

1

2

7

8

9

 

비의 양이 1일 때

9	9	9	9	9	9	9
9	2	1	2	1	2	9
9	1	8	7	8	1	9
9	2	7	9	7	2	9
9	1	8	7	8	1	9
9	2	1	2	1	2	9
9	9	9	9	9	9	9

안전 구역의 개수 : 1개

 

비의 양이 2일 때

9	9	9	9	9	9	9
9	2	1	2	1	2	9
9	1	8	7	8	1	9
9	2	7	9	7	2	9
9	1	8	7	8	1	9
9	2	1	2	1	2	9
9	9	9	9	9	9	9

안전 구역의 개수 : 2개

 

비의 양이 7일 때

9	9	9	9	9	9	9
9	2	1	2	1	2	9
9	1	8	7	8	1	9
9	2	7	9	7	2	9
9	1	8	7	8	1	9
9	2	1	2	1	2	9
9	9	9	9	9	9	9

안전 구역의 개수 : 6개

 

비의 양이 8일 때

9	9	9	9	9	9	9
9	2	1	2	1	2	9
9	1	8	7	8	1	9
9	2	7	9	7	2	9
9	1	8	7	8	1	9
9	2	1	2	1	2	9
9	9	9	9	9	9	9

안전 구역의 개수 : 2개

 

비의 양이 9일 때

9	9	9	9	9	9	9
9	2	1	2	1	2	9
9	1	8	7	8	1	9
9	2	7	9	7	2	9
9	1	8	7	8	1	9
9	2	1	2	1	2	9
9	9	9	9	9	9	9

안전 구역의 개수 : 0개

 

3. 안전 구역의 최대 개수를 결과로 출력합니다.

 

안전 구역 최대 개수 : 6개(비의 양이 7일 때) 결과로 출력합니다.

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 통해서 지역의 높이를 띄어쓰기 기준으로 나누었습니다.
• 내릴 수 있는 모든 비의 양에 대하여 BFS탐색을 진행하여 안전 구역의 개수를 구하였습니다.
• 안전 구역의 최대 개수를 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• copyRegion함수는 임시 지역 정보에 지역 정보를 복사합니다.
• fillRegion함수는 비의 양에 따른 지역 침수 정보를 저장합니다.
• bfs함수는 BFS탐색으로 인접한 침수되지 않은 지역을 묶습니다.
• inSpace함수는 BFS탐색시 지역에 벗어나는지 확인하는 함수입니다.

 

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


public class Main {
    //지역 위치 관련 클래스
    static class position{
        int x, y;
        public position(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
    static int N;
    static int[][] region;		//지역 높이 저장 배열
    static int[][] tempRegion;		//임의 지역 높이 저장 배열
    static boolean[][] visited;		//지역 방문 확인 배열
    static int[] dx = {0, 0, -1, 1};	//상하좌우 X변경 값
    static int[] dy = {-1, 1, 0, 0};	//상하좌우 Y변경 값
    static ArrayList<Integer> list = new ArrayList<>();	//비의 양 저장리스트
    static int answer = 1;
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());
        region = new int[N][N];
        StringTokenizer st;
        //지역 정보 저장
        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());
                if(!list.contains(height))	//비의 양 저장
                    list.add(height);
                region[i][j] = height;
            }
        }
        //모든 비의 양에 따른 안전 구역 개수 구하기
        for(int i=0;i<list.size();i++){
            tempRegion = new int[N][N];
            visited = new boolean[N][N];
            int count = 0;
            copyRegion();		//임시 지역 정보에 지역 정보 복사
            fillRegion(list.get(i));	//비의 양으로 지역 채우기
            //브루트 포스와 BFS로 안전구역 개수 탐색
            for(int j=0;j<N;j++){
                for(int s = 0;s<N;s++){
                    if(tempRegion[j][s] != -1 && !visited[j][s]){
                        bfs(j, s);
                        count++;
                    }
                }
            }
            //안전 구역 개수가 최대값인지 비교
            answer = Math.max(answer, count);
        }
        bw.write(answer + "");	//안전 구역 개수 최대값 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //임시 지역 정보에 입력받은 지역 정보 복사하는 함수
    static void copyRegion(){
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++)
                tempRegion[i][j] = region[i][j];
        }
    }
    //비의 양에 따른 지역에 침수 정보 변경 함수
    static void fillRegion(int height){
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                if(tempRegion[i][j] <= height)
                    tempRegion[i][j] = -1;
            }
        }
    }
    //BFS 탐색으로 안전 구역의 영역 나누기
    static void bfs(int y, int x){
        Queue<position> q = new LinkedList<>();
        q.add(new position(x, y));
        visited[y][x] = true;
        while(!q.isEmpty()){
            position cur = q.poll();
            for(int i=0;i<4;i++){
                int tempX = cur.x + dx[i];
                int tempY = cur.y + dy[i];
                //인접한 구역도 침수되지 않은 지역일 경우
                if(inSpace(tempX,tempY) && !visited[tempY][tempX] && tempRegion[tempY][tempX] != -1){
                    visited[tempY][tempX] = true;
                    q.add(new position(tempX, tempY));
                }
            }
        }
    }
    //지역의 범위를 벗어나지 않는지 확인하는 함수
    static boolean inSpace(int x, int y){
        if(x >=0 && y>=0 && x<N && y<N)
            return true;
        return false;
    }
}