[백준] 2468 안전영역(Java)

문제링크

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

문제분석

• 지도(N X N)에서 일정한 높이 이하의 모든지점 => 물에 잠긴다
• 영역 : 상하좌우로 연결되어 있다. 상하좌우로 연결되어 있다면 같은 영역이다.
  
  위 경우 영역의 개수는 5개다.
• 어떤 지역의 높이 정보가 주어졌을 때, 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수는?
• 주의! 아무 지역도 물에 잠기지 않을 수도 있다 => 물의 높이가 0인 경우도 생각해야 한다.

입력

• N (2<= N <= 100)
• N x N의 높이 정보 (1<= 각 칸 <= 100)

출력

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

풀이

• 입력을 받으며 지도의 최대 높이(maxHeight)를 찾는다.

  • 0 ~ 100까지 모든 높이를 검사하지 않기 위해

• 0 ~ maxHeight 동안 안전 영역의 개수를 센다.

  • ch배열을 선언해 물에 잠김 or 방문한 영역임을 표시

  • 발견하지 않은 지역이 있다면, 개수를 1 추가 후 DFS로 상하좌우 연결된 부분을 체크한다.

    private static int countRegion(int height) {
        int count = 0;
        
        //물에 잠김 or 방문한 영역을 표시할 ch 배열
        boolean[][] ch = new boolean[n][n];
    
    				//물에 잠긴 영역 표시
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
                if(map[i][j]<=height)
                    ch[i][j] = true;
    
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++){
            	//방문하지 않은 지역이 있다면
                if(ch[i][j]==false){
                    count++; //개수 추가
                    DFS(i, j, ch); //연결된 부분 체크 
                }
            }
    
        return count;
    }
    
    private static void DFS(int r, int c, boolean[][] ch) {
    	//상하좌우로 탐색한다.
        for(int i=0; i<4; i++){
            int nr = r+ dr[i];
            int nc = c+dc[i];
    
            if(nr<0 || nr>=n || nc<0 || nc>=n) continue;
            if(ch[nr][nc]==false){
                ch[nr][nc]= true;
                DFS(nr, nc, ch);
            }
        }
    }

전체 코드

import java.util.*;

public class Main {
    //상하좌우 탐색에 사용할 변위
    static int[] dr = {-1, 0, 1, 0};
    static int[] dc = {0, 1, 0, -1};

    static int n;
    static int[][] map;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        map = new int[n][n];
        int maxHeight = Integer.MIN_VALUE;
        int answer = Integer.MIN_VALUE;

        //지도를 입력 받으며 최대 높이 갱신
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                map[i][j] = scanner.nextInt();
                maxHeight = Math.max(maxHeight, map[i][j]);
            }
        }

        //0 ~ maxHeight 동안 안전 영역의 개수를 센다.
        for(int i=0; i<=maxHeight; i++){
            //안전 영역의 최대 개수 갱신
            answer = Math.max(countRegion(i), answer);
        }
        System.out.println(answer);
    }

    private static int countRegion(int height) {
        int count = 0;

        //물에 잠김 or 방문한 영역을 표시할 ch 배열
        boolean[][] ch = new boolean[n][n];

        //물에 잠긴 영역 표시
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
                if(map[i][j]<=height)
                    ch[i][j] = true;

        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++){
                //방문하지 않은 지역이 있다면
                if(ch[i][j]==false){
                    count++; //개수 추가
                    DFS(i, j, ch); //연결된 부분 체크
                }
            }

        return count;
    }

    private static void DFS(int r, int c, boolean[][] ch) {
        //상하좌우로 탐색한다.
        for(int i=0; i<4; i++){
            int nr = r+ dr[i];
            int nc = c+dc[i];

            if(nr<0 || nr>=n || nc<0 || nc>=n) continue;
            if(ch[nr][nc]==false){
                ch[nr][nc]= true;
                DFS(nr, nc, ch);
            }
        }
    }
}