[백준] 안전 영역 2468번 - Java

[백준] 안전 영역 2468번

나의 풀이

public class SafeZone {
    static int[][] graph = new int[100][100];
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static boolean[][] visited;
    static int N;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        StringTokenizer st;

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

        int answer = 0;
        for(int i = 0; i < maxHeight + 1; i++) {
            int count = 0;
            visited = new boolean[100][100];
            for(int x = 0; x < N; x++) {
                for(int y = 0; y < N; y++) {
                    if(dfs(x, y, i)) {
                        count++;
                    }
                }
                answer = (int)Math.max(count, answer);
            }
        }

        System.out.println(answer);
    }

    private static boolean dfs(int x, int y, int i) {
        if(visited[x][y] || graph[x][y] <= i) {
            return false;
        }

        visited[x][y] = true;

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

            if(nx < 0 || ny < 0 || nx >= N || ny >= N) {
                continue;
            }

            if(graph[nx][ny] <= i) {
                continue;
            }

            if(graph[nx][ny] > i && !visited[nx][ny]) {
                dfs(nx, ny, i);
            }
        }

        return true;
    }
}

• dfs를 사용하여 접근하였다. 문제의 요건은 입력되는 높이 보다 큰 값이 몇 개의 구간으로 나뉘어 졌는지를 찾는 것이다. 그렇기 때문에 dfs를 통해서 같은 값이 아닌 보다 큰 값을 탐색해 나가야 한다.
• dfs에서 사용하기 위해 2차 배열과, 방문 배열 등을 클래스 변수로 생성해 준다.
• 반복을 돌며 입력되는 배열의 값을 graph 배열에 담아주고, 입력되는 높이 중에서 가장 높은 값을 구해준다.
• 0부터 최대 높이까지 dfs를 통해서 확인해야 한다. 때문에 0부터 최대 높이 까지의 반복문을 가장 밖에 작성한다. 그리고 배열을 다 돌 때마다 방문 기록과 count는 초기화 되야 하기 때문에 초기화 될 수 있도록 작성해 주었다. 이제 2차 배열을 돌면서 dfs에 파라미터로 좌표와 높이를 넘겨준다.
• 만약 입력된 좌표를 방문한 적이 있거나, 해당 좌표의 값이 최대 높이보다 작다면 false를 리턴한다.
• 아니라면 해당 좌표를 방문처리 해준다.
• 그리고 네 방향을 체크해준다. 만약 상, 하, 좌, 우 가 배열의 범위를 벗어난다면, 다음 해당 방향은 continue를 통해서 스킵해준다.
• 그리고 만약 상, 하, 좌, 우 중에서 해당 좌표를 가진 graph의 값이 i보다 작거나 같다면 조건에 부합하기 때문에 이 또한 continue로 스킵해준다.
• 마지막으로 상, 하, 좌, 우 중에서 해당 좌표를 가진 graph의 값이 i보다 크고, 방문 기록이 없다면, 재귀호출을 통해 계속 탐색해 나간다. 탐색을 마치면 true를 리턴하게 되고, if문을 통해서 count가 1 증가한다.
• 이 과정을 반복하면 해당 높이보다 큰 구간이 몇 개 인지 알 수 있다.
• 마지막으로 count의 최댓값을 구해야 하기 때문에 Math.max를 사용하여 최댓값 비교를 해줘야 한다.