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

24609 단어 DFSDFS

문제링크

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);
            }
        }
    }
}

좋은 웹페이지 즐겨찾기