[Algorithm] 백준_안전 영역_2648번 (JAVA)

📝문제

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

티어 : 실버1

 

💡풀이

 

문제 유형

dfs

 

걸린 시간

37분

 

시간 복잡도

O(N^2)

최악의 경우 -> O(100*100*100) => 1000000번의 연산 => 1초 안에 ok

 

풀이 방법 도출

1. 구역 나누기 => dfs로 풀이 가능
2. h를 증가시키면서 가장 큰 값이 나오는 경우를 저장해 두는 방법을 사용했다.
3. h=0으로 두고 while 반복문을 돌린다.
4. 이때 구역의 수를 count로 두고 count가 0이 되면 반복문을 빠져나온다.  => 모든 위치를 다 방문함
5. 현재 위치의 높이가 h보다 높거나 같고, 방문하지 않은 위치라면 dfs를 돌려 현재 위치부터 사면을 검사해 방문을 체크해 준다.
6. 정답 max와 count 중 더 큰 값을 max에 저장하고 답을 출력한다.

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

class Main {
    static int N;
    static int[][] arr;
    static boolean[][] visited;

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

        N = Integer.parseInt(br.readLine());
        arr = new int[N][N];
        visited = new boolean[N][N];
        StringTokenizer st;

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        int h = 0;
        int max = 0;
        int count = 1;
        while (count != 0) {
            h++;
            count = 0;
            visited = new boolean[N][N];
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (arr[i][j] >= h && !visited[i][j]) {//안전한 영역
                        visited[i][j] = true;
                        count++;
                        dfs(i, j, h);
                    }
                }
            }
            max = Math.max(max, count);
        }
        System.out.println(max);
    }

    public static void dfs(int x, int y, int h) {
        int[] dx = {0, 1, 0, -1};
        int[] dy = {1, 0, -1, 0};

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx >= 0 && nx < N && ny >= 0 && ny < N) {
                if (!visited[nx][ny] && arr[nx][ny] >= h) {
                    visited[nx][ny] = true;
                    dfs(nx, ny, h);
                }
            }
        }
    }
}

 

🤔Review

백준은 한 번에 맞출 때가 제일 쾌감 있지