[백준] 2468번 안전 영역 JAVA (자바) 풀이

문제 2468 (dfs, 백트래킹)

• 지역의 높이 정보를 파악
• 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사
  
  
• 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정
• 각 지역의 높이 정보 = N크기의 2차원 배열 형태
• 배열의 각 원소 = 높이
  
  
• 침수 정도를 어떤 높이로 설정해야 안전한 영역이 최대가 되는지 계산해라
  
  

예) N=5 → 5 x 5 배열

 

6	8	2	6	2
3	2	3	4	6
6	7	3	3	2
7	2	5	3	6
8	9	5	2	7

 

• 높이가 4 이하인 지점 물에 잠겼다 = 회색

6	8	2	6	2
3	2	3	4	6
6	7	3	3	2
7	2	5	3	6
8	9	5	2	7

→  안전한 영역 = 물에 잠기지 않는 지점 상, 하, 좌, 우로 인접하며 그 크기가 최대인 영역

→  안전한 영역 = 5개

 

• 높이가 6이하인 지점이 잠긴다면 안전한 영역은 4개

6	8	2	6	2
3	2	3	4	6
6	7	3	3	2
7	2	5	3	6
8	9	5	2	7

 

 

[입력]

 : 첫째 줄에는 어떤 지역을 나타내는 배열의 행과 열의 개수 N ( N은 2 이상 100 이하의 정수)

 

 :  둘째 줄부터 N번째까지 높이 정보를 빈칸으로 구별해 입력 (높이는 1이상 100 이하의 정수)

5
6 8 2 6 2
3 2 3 4 6
6 7 3 3 2
7 2 5 3 6
8 9 5 2 7

 

 

 [출력]

 :  물에 잠기지 않는 안전한 영역의 최대 개수를 출력

5

 

 

 

 [문제접근]

 

• 모든 경로를 하나하나 다 파악해줘야 하기 때문에 DFS 선택!
  
  
• 침수 당하는 높이의 height 를 0부터 시작해서 쭉 검사
  
  → 어느 부분에서 안전영역 수가 최대가 될 지 모르니 하나하나 다 해보는 것
  → 2차원 배열판에 적힌 수 중에 가장 큰 수가 height의 limit이다
  
  
• dfs로 안전한 지점의 인접한 부분 싹 다 확인하고 count
  
  → 배열 안에 들어가 있는지 확인 / 침수되지 않았는지 확인 / 아직 방문 전인지 확인
  → 위 조건들이 확인 되었으면 인접한 위치로 이동한 새 위치를 다시 dfs로 넘겨서 방문처리 반복
  → 더 이상 방문할 곳이 없다면 dfs 종료하고 안전한 영역이라고 count 하기 
  
  
• count 중에서 max 값 뽑아서 result로 출력
  

 [코드]

import java.io.*;
import java.util.*;
public class Main{
    static int N;
    static int limit = 0; 
    static int dx[] ={0,0,1,-1};
    static int dy[] ={1,-1,0,0};
    static int map[][];
    static boolean visit[][];
    
    public static void main(String[]args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        int result = 0;
        
        for(int i = 0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j<N; j++){
                map[i][j]=Integer.parseInt(st.nextToken());
                limit = Math.max(limit,map[i][j]);
            }
        }
        
        for(int h = 0; h<=limit; h++){
            visit = new boolean[N][N];
            int count = 0;
            for(int i =0; i<N; i++){
                for(int j=0; j<N; j++){
                    if(!visit[i][j] && map[i][j]>h){
                        dfs(i, j, h);
                        count++;
                    }
                }
            }
            result = Math.max(result,count);
        }
        System.out.println(result);
        
    }
    public static void dfs(int x, int y, int height){
        visit[x][y] = true;
        
        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(0<=nx&&nx<N && 0<=ny&&ny<N && map[nx][ny]>height && !visit[nx][ny]){
                dfs(nx, ny, height);
            }   
        }
    }
}

 

 

 [해설]
     

 :  static int N;  배열판 범위
    static int limit = 0;  침수 최대 기준 높이
    static int dx[] ={0,0,1,-1};  상하좌우 이동
    static int dy[] ={1,-1,0,0};  상하좌우 이동
    static int map[][];  2차원 배열판
    static boolean visit[][];  방문기록
      

 :  N = Integer.parseInt(br.readLine());  첫번째 줄 입력
    map = new int[N][N];  배열판 초기화
    int result = 0;  결과값 초기화

 

 :  for(int i = 0; i<N; i++){ 
         st = new StringTokenizer(br.readLine());  
         for(int j = 0; j<N; j++){
             map[i][j]=Integer.parseInt(st.nextToken());  배열판에 각 높이 입력
             limit = Math.max(limit,map[i][j]);  입력된 높이 중 가장 max값을 limit으로 정하기
         }
    }
       

 :  for(int h = 0; h<=limit; h++){  모두 침수되지 않을 ~ 모두 침수될 경우 반복
         visit = new boolean[N][N];  방문기록 매번 침수 기준 바뀔 때마다 초기화
         int count = 0;  안전영역 count 침수 기준 바뀔 때마다 초기화
       
         for(int i =0; i<N; i++){  
             for(int j=0; j<N; j++){
                 if(!visit[i][j] && map[i][j]>h){  방문하지 않았고 침수되지 않았으면 dfs 시작
                      dfs(i, j, h);  dfs 실행 
                      count++;  dfs의 모든 과정이 끝나면 하나의 안전한 영역으로 count
                 }
             }
         }
         result = Math.max(result,count);  침수 기준별로 count된 최대 result 선정
    }
    System.out.println(result);  결과 출력
  

 :  public static void dfs(int x, int y, int height){
        visit[x][y] = true;  지점 넘어올 때마다 방문처리부터 하고 시작
        
        for(int i=0; i<4; i++){  인접한 위치로 이동
            int nx = x + dx[i];  현위치 x좌표
            int ny = y + dy[i];  현위치 y좌표
            if(0<=nx&&nx<N && 0<=ny&&ny<N && map[nx][ny]>height && !visit[nx][ny]){  
                dfs(nx, ny, height);  인접한 위치로 이동한 현지점이 침수되지 않았고 방문 전이라면 dfs 반복
            }   
        }
    }
 

 

이제 풀어보러 갈께요 :)

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *

 

2468번: 안전 영역