[백준 - JAVA] 2468번 : 안전 영역

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

2468번: 안전 영역

전형적인 DFS, BFS 문제에 효율성을 추가한 문제이다.

아무것도 안 잠기는 경우 = 안전 영역 1개

그 외에 판단해야 하는 경우 각 위치의 높이가 해당하는 지점

예를 들면 높이가 (1, 2, 2, 3, 3, 4, 8) 이라면, 1, 2, 3, 4, 8 일때 확인함으로서 확인 횟수를 줄일 수 있다.

=> Set을 사용해서 중복된 높이를 지웠다.

 

이번에는 dfs로 풀어보고 싶었는데 최악의 경우에 스택이 10000개 쌓이는데 최대 call stack depth가 얼마인지 궁금했다.

일정이 바빠서 많은 공부는 못했다. 관련 링크 하나만 남기고 일정 끝나고 다시 돌아와서 정리하겠다.

기본적으로 자바에서 얼마나 깊이 사용할 있는지는 명시해두지 않았다.

컴퓨터마다 다르다고 하는데 이런 위험성을 감수하는 것보다 큐를 사용하는 bfs가 더 안정적이라는 생각을 했다.

스택 사이즈를 확인할 수 있는 방법은 아래 사이트에 설명되어 있다.

http://www.odi.ch/weblog/posting.php?posting=411 

Java stack size myths

그리고 이 문제는 최악의 경우에 100*100*100 번 확인을 해야하는데 백만 정도면 1초안에 확인이 될 것이기 때문에 dfs로 접근했다.

구현 코드는 다음과 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Q_2468 {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static Set<Integer> set = new HashSet<>();
    static int[][] map;
    static boolean[][] visited;
    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, 1, -1};
    static int result = 1;
    static int N, cnt;
    public static void main(String[] args) throws IOException {
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];

        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());
                set.add(map[i][j]);
            }
        }
        List<Integer> list = new ArrayList<>(set);

        for(int i = 0; i < list.size(); i++) {
            solution(list.get(i));
        }

        System.out.println(result);

    }

    private static void solution(int height) {
        //모든 높이마다 확인
        visited = new boolean[N][N];
        cnt = 0;

        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                //방문했다면 넘어가
                if(visited[i][j] == true) {
                    continue;
                }

                //잠긴 곳이라면 방문처리하고 넘어가
                if(map[i][j] <= height) {
                    visited[i][j] = true;
                    continue;
                }

                //방문하지 않았고 섬이라면 체크
                cnt++;
                //모든 섬 체크
                dfs(i, j, height);
            }
        }

        result = Math.max(result, cnt);
    }

    private static void dfs(int i, int j, int height) {
        //모든 점에 대해서 확인 DFS로 확인해보자.
        //혹시 스택의 깊이가 어디까지 내려갈 수 있을까? 만개도 버틸 수 있나?

        //일단 범위 안에 들어 왔는지 체크
        if(!isInRange(i, j)) return;

        //방문 했는지 체크
        if(visited[i][j]) return;

        //잠긴 곳이라면 방문처리하고 넘어가
        if(map[i][j] <= height) {
            visited[i][j] = true;
            return;
        }

        visited[i][j] = true;

        for(int d = 0; d < 4; d++) {
            int nr = i + dr[d];
            int nc = j + dc[d];
            dfs(nr, nc, height);
        }

    }

    private static boolean isInRange(int i, int j) {
        if(i < 0 || N <= i || j < 0 || N <= j) {
            return false;
        }
        return true;
    }
}