[백준] dfs - 2648번 안전영역 (Java)

문제링크

2468번: 안전 영역

 

 

접근한 방법

• 구역을 구하는 문제이므로
  dfs

 

---

풀이방법

비의 양보다 큰 값이 상, 좌, 하, 우로 연결되어 있는 범위를 묶어 그 안의 있는 요소의 수를 세면된다.

1. 특정한 지점의 주변 상, 좌, 하, 우를 살펴본 뒤에 주변 지점 중에서 값이 비의 양보다 크면서 아직 방문하지 않은 지점이 있다면 해당 지점을 방문한다.
2. 방문한 지점 에서 다시 상, 좌, 하, 우를 살펴보면서 방문을 다시 진행하면, 연결된 모든 지점을 방문할 수 있다.
   방문시마다 요소의 수를 더해준다.
3. 1~2번의 과정을 모든 노드에 반복

4. 값을 비교하여 큰 값을 저장

 

---

 

소스코드 작성 방법

• 입력받을 때 건물의 최대 높이를 얻는다.
• 맵의 크기(n)를 전역 필드로 선언한다.
• 영역의 정보(map), 방문 여부(visitied)를 전역 필드로 선언한다.
• 각 영역의 의 개수(count)를 전역 필드로 선언한다.
• 영역의 개수(result)를 전역 필드로 선언한다.
• 방향 배열 dx, dy로 상 좌 하 우 움직임을 저장한다.
• dfs 메소드의 노드 번호(curR, curC)와 비의 양(rain)을 인자로 받는다.
  • vistied[curR][curC] = true로 하여 방문 처리
  • nextR, nextC를 for문 안에 선언하여 현재 위치에서 상 좌 하 우 위치를 탐색한다.
    • nextR은 curR + dx[dir]
      nextC는 curC + dx[dir] 로 상 좌 하 우 값을 선언해준다.
    • 상 좌 하 우 위치 이동 시 n*n배열의 크기보다 크면 continue하여 넘어간다.
    • map[nextR][nextC] > rain이고 (비의 양보다 건물이 높으면) visited[nextR][nextC] = false로 아직 방문하지 않았다면
      dfs 메소드를 재귀적으로 호출하여 방문수행
• solution 메소드에서 비의 양이 없을 때(0)부터 비의 양이 건물의 최대높이보다 클 때까지를 기준으로
  (0,0)노드부터 (n-1,n-1)노드까지 방문을 수행한다.
  * 방문하지 않은 노드만 방문 수행 !
  • 방문이 끝난 후에, count++하여 영역 개수를 추가하고
    노드 탐색이 모두 끝나면, count = 0으로 초기화한다.

 

소스코드

package baekjoon.dfs_bfs;
import java.io.*;
import java.util.StringTokenizer;

public class Q_2468_SaftyArea_20210614 {
    public static int n;
    public static int maxHeight;
    public static int[][] map;
    public static boolean[][] visited;
    public static int[] dx = {-1, 0, 1, 0};
    public static int[] dy = {0, -1, 0, 1};
    public static int count;
    public static int result;

    public static int solution(){
        for(int rain = 0 ; rain <= maxHeight+1 ; rain++){
            visited = new boolean[n][n];
            for (int r = 0; r < n; r++) {
                for (int c = 0; c < n; c++) {
                    if(!visited[r][c] && map[r][c] > rain) {
                        dfs(r, c, rain);
                        count++;
                    }
                }
            }
            result = Math.max(result, count);
            count = 0;
        }

        return result;

    }

    public static void dfs(int curR, int curC, int rain){
        visited[curR][curC] = true;

        for(int dir = 0 ; dir<4 ; dir ++){
            int nextR = curR + dx[dir];
            int nextC = curC + dy[dir];

            if(nextR <0 || nextC <0 || nextR >=n || nextC >=n) continue;
            else if(!visited[nextR][nextC] && map[nextR][nextC] > rain)
                dfs(nextR, nextC, rain);
        }

    }

    public static void main (String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        n = Integer.parseInt(br.readLine());
        map = new int[n][n];
        visited = new boolean[n][n];
        for(int i=0 ; i<n ; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                maxHeight = Math.max(maxHeight, map[i][j]);
            }
        }

        bw.write(solution()+"");

        br.close();
        bw.close();
    }
}