[BOJ/백준] 1245 - 농장 관리 (Java/G5)

BOJ - 1245 농장 관리

1245번: 농장 관리

 

🏷️ 카테고리

#그래프 이론 #그래프 탐색 #BFS #DFS

 

⏳ 시간복잡도

O(n)

 

📒 해설

그래프 탐색을 익혀볼 수 있는 문제입니다. 그래프 탐색을 연습할 수 있는 대표적인 문제인 토마토이나 적록색약과 같은 느낌의 문제로 '산봉우리를 어떻게 계산할지'를 고민하면서 그 조건을 BFS 혹은 DFS에 접목시키는 것이 포인트입니다.

📜 문제 조건

농장관리 - 문제 조건

농장관리 문제에서 주어진 조건은 다음과 같습니다. 

• 농장은 N * M 형태의 2차원 배열의 형태로 주어진다. N은 1 이상, 100 이하, M은 1 이상 70 이하의 수로, 2차원 배열에서 존재할 수 있는 격자의 최대 수는 7000이다. 즉 모든 격자를 탐색해도 2초 이내에 수행이 가능하다.
• 산봉우리는 같은 높이를 가진 인접한 칸들의 집합이다. 
• '인접하다'는 X좌표의 차이, Y좌표의 차이가 모두 1이하일 때를 의미한다. 즉, 2차원 배열에서 기준점을 둘러싼 8방향의 지점을 의미한다.
• 산봉우리의 개수를 출력해야한다.

🔍 문제 접근

문제 조건을 통해 농장의 모든 격자를 탐색해도 시간이 충분하다는 사실을 알 수 있습니다.

그렇다면 어떤 방법을 통해서 모든 격자를 탐색할 지에 대해서 고민을 해야 합니다. 앞서, 해설 부분에서 '산봉우리를 어떻게 계산할지'에 대해서 생각이 든 것은 두 가지 방법이 있었습니다.

 

 

방법 1

 

처음 생각한 방법은 인접한 격자 중, 자신과 같거나 작은 부분을 같은 영역으로 탐색을 하면서, 인접한 영역 중 속한 영역 중 가장 큰 값보다 더 큰 값이 나온다면, 해당 영역은 산봉우리가 될 수 없다고 체크를 해주는 방법을 생각했습니다.

 

그 방법대로 진행하면, 이런 형태의 결과가 나오게 된다. 같은 색을 띠고 있는 격자는 같은 영역으로 취급하고 산봉우리가 될 수 있는 영역은 노란색, 파란색, 빨간색으로 3개가 됩니다.

이 결과는 주어진 테스트케이스는 통과할 수 있지만, 반례가 존재했습니다.

 

이는 실제 산봉우리가 아닌, 더 낮은 지역에서 가장 높은 지역보다 더 높은 지역을 만났다고 판단해서 산봉우리가 아니라고 생각되는 경우입니다.

 

 

방법 1을 사용하면 위와 같은 케이스에서 실제 답은 4지만 답이 3이 나옵니다.

그 이유는 노란색 영역에서 3으로 이루어진 부분에서 산봉우리가 형성될 수 있는데, 탐색을 진행하다가 보라색 4와 인접한 격자들이 더 높은 봉우리를 만났다고 판단하고 산봉우리가 아니라고 판단할 수 있기 때문입니다.

 

 

방법 2

 

그다음으로 생각한 방법은, 위와 비슷하지만, 탐색을 진행할 때 자신과 동일한 높이의 격자만을 연합으로 삼는 방법입니다.

 

 

위와 같은 형태의 결과가 나타나게 되고, 테스트 케이스의 정답인 산봉우리가 3개인 것을 확인할 수 있습니다.

 

방법 1의 반례 또한 이 방법을 이용하면 산봉우리를 4개로 계산합니다.(빨강, 파랑, 보라, 회색)

🔑 문제 풀이

 

사용 변수

static int [][] matrix; // 농장의 격자를 표현하는 2차원 배열
static boolean[][] visited; // bfs를 진행하기 위한 방문 배열
static int nOfTop; // 산봉우리 개수
static Position[] deltas = { // 8방 탐색을 위한 배열
        new Position(-1,-1),
        new Position(-1,0),
        new Position(-1,1),
        new Position(0,-1),
        new Position(0,1),
        new Position(1,-1),
        new Position(1,0),
        new Position(1,1),
};

static int n,m; // 농장의 크기
static Queue<Position> q; // bfs를 진행할 때 사용되는 queue

static class Position{ // 8방 탐색과 bfs에서 사용될 좌표 정보
    int row;
    int col;

    public Position(int row, int col) {
        this.row = row;
        this.col = col;
    }
}

 

전체 농장 탐색

for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        if (visited[i][j]) continue;
        if(bfs(i,j))
            nOfTop++;
    }
}

농장의 모든 격자에 대해서 BFS를 진행합니다. bfs의 결과에 따라서 해당 지점이 산봉우리가 맞다면, nOfTop(산봉우리 개수)를 1 더해줍니다.

BFS

static boolean bfs(int row, int col){
    q.add(new Position(row, col));
    int height = matrix[row][col];
    visited[row][col] = true;
    boolean isTop = true;

    while (!q.isEmpty()) {
        Position pos = q.poll();

        for (Position del : deltas) {
            int nr = pos.row + del.row;
            int nc = pos.col + del.col;
            if (isIn(nr, nc)) {
                // 크기 비교
                if (matrix[nr][nc] > height) {
                    isTop = false;
                }else{
                    if (!visited[nr][nc] && matrix[nr][nc] == height) {
                        visited[nr][nc] = true;
                        q.add(new Position(nr,nc));
                    }
                }
            }
        }
    }
    return isTop;
}

bfs를 진행하는 코드입니다. 방법 2에서 설명했듯이, 8방향에 대해서 탐색하며 인근에 더 큰 값이 존재한다면 산봉우리가 될 수 없다는 의미로 isTop 변수를 false로 만들어줍니다. 그리고 탐색을 할 때엔 처음 지점과 같은 크기의 격자를 탐색합니다. 

전체 코드

package study.d0914;

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


/**

@author 규현
@since 2023-09-10
@url https://www.acmicpc.net/problem/1245
@level G5
@try 1
@performance 13200KB, 108ms 16min
@category #그래프 이론, #그래프 탐색, #BFS #DFS
@note
 산 봉우리의 개수를 세는 문제이다.
 민식이의 땅은 N * M의 형태로 주어진다.
 산 봉우리란 같은 높이를 가진 집단인데, 인접한 애들은 자기보다 작아야 한다.


 인접하다 : x좌표 혹은 y좌표의 차이가 모두 1보다 작은 경우이다.
          즉 자기 위치로부터 8방향 내에 있는 애들은 모두 인접한 것.

 BFS를 통해서 접근하려고 한다.
 0,0부터 n-1,m-1 까지 bfs를 반복하면서 산봉우리를 찾는다. 시작 지점을 기준으로, 8방 탐색을 진행하면서
 탐색을 한다. 탐색을 하는 기준은 자기와 크기가 같은 애들을 넣는다. 탐색하는 과정에서 8방향 내에 자신보다 큰
 격자를 찾으면, 체크를 하여, 해당 지점이 산봉우리가 아님을 표기한다.

 높이를 비교할 때엔 bfs의 방문배열과 무관하게 진행한다.

*/
public class 농장관리 {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;

    static int [][] matrix; // 농장의 격자를 표현하는 2차원 배열
    static boolean[][] visited; // bfs를 진행하기 위한 방문 배열
    static int nOfTop; // 산봉우리 개수
    static Position[] deltas = { // 8방 탐색을 위한 배열
            new Position(-1,-1),
            new Position(-1,0),
            new Position(-1,1),
            new Position(0,-1),
            new Position(0,1),
            new Position(1,-1),
            new Position(1,0),
            new Position(1,1),
    };

    static int n,m; // 농장의 크기
    static Queue<Position> q; // bfs를 진행할 때 사용되는 queue



    public static void main(String[] args) throws Exception {
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        matrix = new int[n][m];
        visited = new boolean[n][m];
        q = new ArrayDeque<>();

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                matrix[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (visited[i][j]) continue;
                if(bfs(i,j))
                    nOfTop++;
            }
        }

        System.out.println(nOfTop);


    }

    static boolean bfs(int row, int col){
        q.add(new Position(row, col));
        int height = matrix[row][col];
        visited[row][col] = true;
        boolean isTop = true;

        while (!q.isEmpty()) {
            Position pos = q.poll();

            for (Position del : deltas) {
                int nr = pos.row + del.row;
                int nc = pos.col + del.col;
                if (isIn(nr, nc)) {
                    // 크기 비교
                    if (matrix[nr][nc] > height) {
                        isTop = false;
                    }else{
                        if (!visited[nr][nc] && matrix[nr][nc] == height) {
                            visited[nr][nc] = true;
                            q.add(new Position(nr,nc));
                        }
                    }
                }
            }
        }
        return isTop;
    }

    // 다음 탐색할 위치가 2차원 배열 내에 가능한 좌표인지 체크
    static boolean isIn(int row, int col){
        return row >= 0 && row <n && col >= 0 && col < m;
    }


    static class Position{ // 8방 탐색과 bfs에서 사용될 좌표 정보
        int row;
        int col;

        public Position(int row, int col) {
            this.row = row;
            this.col = col;
        }
    }


}

결과