[백준 1245] 농장 관리 - JAVA

BOJ Link

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

 

유의할 점

명시되지 않은 조건이 있다.

=> 산봉우리의 높이는 0이 될 수 없다.

 

모호한 조건이 있다.

=> 산봉우리는 같은 높이를 가지는 하나의 격자 혹은 인접한 격자들의 집합으로 이루어져 있다.

 

이에 따라, 고려할 케이스

// input
3 3
0 0 0
0 0 0
1 0 1

// output
2 // ans
1 // wrong ans

 

풀이 이후, assert로 N=1 / M=1인 케이스는 없음을 확인했다.

제출 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;

class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int R = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());

        int[][] map = new int[R][C];
        boolean[][] visited = new boolean[R][C];

        int ans = 0;

        int[] dr = {0, 0, -1, 1, -1, -1, 1, 1};
        int[] dc = {-1, 1, 0, 0, -1, 1, -1, 1};

        for (int i = 0; i < R; i++) {
            map[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        }

        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {

                if (!visited[i][j]) {
                    boolean flag = true;
                    Queue<int[]> q = new ArrayDeque<>();
                    boolean[][] compared = new boolean[R][C];

                    visited[i][j] = true;
                    compared[i][j] = true;
                    int peak = map[i][j];

                    if (peak != 0) {
                        q.offer(new int[]{i, j});

                        while (!q.isEmpty()) {

                            int[] info = q.poll();

                            for (int k = 0; k < 8; k++) {
                                int tr = info[0] + dr[k];
                                int tc = info[1] + dc[k];
                                if (tr >= 0 && tr < R && tc >= 0 && tc < C && !compared[tr][tc]) {

                                    int tv = map[tr][tc];
                                    if (tv == peak) {
                                        visited[tr][tc] = true;
                                        compared[tr][tc] = true;
                                        q.offer(new int[]{tr, tc});
                                    } else if (tv > peak) {
                                        flag = false;
                                    }
                                }
                            }

                        }
                        if (flag) ans++;
                    }
                }
            }
        }

        System.out.println(ans);
    }
}