[백준 1245] - 농장 관리 Java

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

1245번: 농장 관리

문제를 간단하게 정리하면

특정 좌표에 특정 산 A의 높이가 표시되어 있는데, 둘러싸인 주변 산의 높이는 A보다 낮아야한다.

문제에서의 예제를 분석해보면 확실하게 이해할 수 있는데

8 7
4 3 2 2 1 0 1
3 3 3 2 1 0 1
2 2 2 2 1 0 0
2 1 1 1 1 0 0
1 1 0 0 0 1 0
0 0 0 1 1 1 0
0 1 2 2 1 1 0
0 1 1 1 2 1 0

위 예제에서 산봉우리는 (왼쪽 맨 위를 0,0으로 가정)

1. (0,0)의 높이 4인 땅과 둘러싸인 3 높이의 땅 (높이 4인 땅 주위로 4보다 큰 땅이 없다)
2. (6,0)과 (6,1)의 높이 1인 땅과 둘러싸인 높의 0의 땅
3. (2,6), (3,6), (4,7)의 높이 2인 땅과 둘러싸인 높이 0과 1의 땅

이렇게 3개의 산봉우리가 존재하게 된다.

한 산봉우리는 3번 예제처럼 대각선으로 붙어있어도 인정된다라는 것을 인지해야한다.

그래서 한 개의 산봉우리의 위치를 구하고

산봉우리 주변을 탐색하여 산봉우리보다 더 낮은 집합으로 이루어져있는지를 알아보면 된다.

풀이

문제를 해결하는 과정은 다음과 같다.

1. 전체를 순회하며 아직 방문하지 않은 한 개의 땅의 높이를 선택한다.
2. 선택한 높이와 같은 산봉우리 집합을 구한다 (dfs)
3. 구한 같은 높이의 산봉우리를 큐에 넣고, 하나씩 꺼내면서 주변 한 칸씩 검사한다.
   • 모든 주변의 한 칸이 전부 산봉우리보다 낮으면 true
   • 만족하지 않으면 모두 false
     
     이 때 주변 한 칸은 위에서 구한 높이보다 같거나 작아야한다.

 

위 과정을 코드로 나타내면

for(int i =0;i<N;i++) {
    for(int j = 0;j<M;j++) {
        if(!visited[i][j]) {
            search(i, j, map[i][j]);
        }
    }
}

아직 방문하지 않은 땅의 검색을 시작한다.

static void search(int y,int x, int value) {
    q = new ArrayDeque<>();
    searchDetail(y, x, value);
    if(bfs(value)) {
        count++;
    }
}

선택한 후에는, DFS 함수인 searchDetail을 통해 같은 높이의 산봉우리들을 모두 큐에 넣으며 방문처리한다.

static void searchDetail(int y,int x, int value) {
    q.add(new Point(y, x));
    visited[y][x] = true;
    for(int i= 0;i<8;i++) {
        int Y = y + dy[i];
        int X = x + dx[i];
        if (Y >= 0 && X >= 0 && Y < N && X < M && map[Y][X]==value&&!visited[Y][X]) {
            searchDetail(Y,X,value);
        }
    }

}

이 때 방문처리를 해도 되는 이유는

만약 뒤에서 산봉우리를 만족하지 않아 false가 반환되면, 그 땅은 절대 산봉우리의 최대 높이가 될 수 없기 때문에 상관이 없다.

DFS탐색을 마치고 나면

static boolean bfs(int value) {
    while(!q.isEmpty()) {
        Point now = q.poll();

        for(int i = 0;i<8;i++) {
            int Y = dy[i] + now.y;
            int X = dx[i] + now.x;

            if(Y>=0&&X>=0&&Y<N&&X<M) {
                if ((map[Y][X] == value || map[Y][X] < value)) {

                }

                else {
                    return false;
                }
            }
        }
    }
    return true;

}

bfs의 방식으로 1-depth만큼 탐색해서, 조건을 만족하면 while문을 탈출하여 true를 반환하여 count를 증가하게 된다.

전체 코드

package 백준_2024년.스터디_5wnck;

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

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

    static class Point{
        int y,x;

        @Override
        public String toString() {
            final StringBuffer sb = new StringBuffer("Point{");
            sb.append("y=").append(y);
            sb.append(", x=").append(x);
            sb.append('}');
            return sb.toString();
        }

        public Point(int y, int x) {
            this.y = y;
            this.x = x;
        }
    }
    static ArrayDeque<Point> q;
    static boolean bfs(int value) {
        while(!q.isEmpty()) {
            Point now = q.poll();

            for(int i = 0;i<8;i++) {
                int Y = dy[i] + now.y;
                int X = dx[i] + now.x;

                if(Y>=0&&X>=0&&Y<N&&X<M) {
                    if ((map[Y][X] == value || map[Y][X] < value)) {

                    }

                    else {
                        return false;
                    }
                }
            }
        }
        return true;

    }
    static int count = 0;
    static void search(int y,int x, int value) {
        q = new ArrayDeque<>();
        searchDetail(y, x, value);
        if(bfs(value)) {
            count++;
        }
    }
    static void searhDetail(int y,int x, int value) {
        q.add(new Point(y, x));
        visited[y][x] = true;
        for(int i= 0;i<8;i++) {
            int Y = y + dy[i];
            int X = x + dx[i];
            if (Y >= 0 && X >= 0 && Y < N && X < M && map[Y][X]==value&&!visited[Y][X]) {
                searchDetail(Y,X,value);
            }
        }

    }

    static boolean[][] visited ;
    static int[][] map;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
         N = Integer.parseInt(st.nextToken());
         M = Integer.parseInt(st.nextToken());
        map = new int[N][M];
        visited = new boolean[N][M];

        for(int i =0;i<N;i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0;j<M;j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        for(int i =0;i<N;i++) {
            for(int j = 0;j<M;j++) {
                if(!visited[i][j]) {
                    search(i, j, map[i][j]);
                }
            }
        }

        System.out.println(count);

    }
}