백준 1245 - 농장 관리

문제

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

리뷰

DFS를 이용해 풀이할 수 있는 문제였다. 산봉우리의 조건을 세심히 체크해야 하는데
이 부분이 부족하여 오답을 몇 번 마주하였다.

문제에서 얘기하는 산봉우리의 정의는 다음과 같다.

• 같은 높이의 격자들로 이루어져 있다.
• 산봉우리내 격자들의 위치에서 인접한 8방향의 격자들은 모두 산봉우리보다 높이가 작아야 한다.
  위 조건에 따르면 높이가 0인 산봉우리는 애초에 존재할 수 없으므로 0은 무시하여도 된다.

질문 게시판의 테스트 케이스에 따르면 0값을 무시해도 정상 풀이되는 것 같다.
또한, 모두 같은 높이를 가지는 격자가 주어질 경우에도 하나의 산봉우리로 취급한다.

이 조건에 따라 전체 격자에 대하여 dfs 를 실행하고 dfs 내부에서

• 인접한 격자중 높이가 높은 것이 있다면 산봉우리가 아님을 isTop 변수를 통해 표현
• 인접한 격자중 높이가 같은 것이 있다면 같은 봉우리내 속하므로 탐색을 진행
  위와 같은 절차로 로직을 수행하여 isTop이 성립될 때만 카운팅해 답을 도출했다.

로직의 시간복잡도는 dfs를 $O(NM)$의 반복문 내에서 실행하고 있으므로
최악의 경우 $O((NM)^2)$으로 표현되고 이는 제한 조건인 2초를 무난히 통과할 수 있다.

코드

import java.util.Scanner;
import java.util.StringTokenizer;

import static java.lang.Integer.parseInt;

public class Main {
    static int[] dx = {0, 1, 1, 1, 0, -1, -1, -1};
    static int[] dy = {-1, -1, 0, 1, 1, 1, 0, -1};

    static int[][] map;
    static boolean[][] visited;
    static boolean isTop=false;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        StringTokenizer st = new StringTokenizer(in.nextLine());
        int N = parseInt(st.nextToken());
        int M = parseInt(st.nextToken());

        map = new int[N][M];
        visited = new boolean[N][M];


        for (int y = 0; y < N; y++) {
            st = new StringTokenizer(in.nextLine());
            for (int x = 0; x < M; x++) {
                map[y][x] = parseInt(st.nextToken());
            }
        }


        int count = 0;
        for (int y = 0; y < N; y++)
            for (int x = 0; x < M; x++) {
                if(!visited[y][x] && map[y][x]!=0){
                    isTop=true;
                    dfs(new Point(x, y));
                    if(isTop)
                        count++;
                }
            }

        System.out.print(count);
        in.close();
    }

    static void dfs(Point current) { // O(NM)
        visited[current.y][current.x] = true;

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

            if (nx < 0 || nx >= map[0].length || ny < 0 || ny >= map.length)
                continue;

            if (map[ny][nx] > map[current.y][current.x])
                isTop = false;

            if (!visited[ny][nx] && map[ny][nx] == map[current.y][current.x])
                dfs(new Point(nx, ny));
        }
    }


    static class Point {
        int x, y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

결과