[BOJ][🟡5][백준#01245] 농장 관리

문제 출처

BAEKJOON Online Judge #1245

문제

농부 민식이가 관리하는 농장은 N×M 격자로 이루어져 있다. 민식이는 농장을 관리하기 위해 산봉우리마다 경비원를 배치하려 한다. 이를 위해 농장에 산봉우리가 총 몇 개 있는지를 세는 것이 문제다. 산봉우리의 정의는 다음과 같다. 산봉우리는 같은 높이를 가지는 하나의 격자 혹은 인접한 격자들의 집합으로 이루어져 있다. (여기서 “인접하다”의 정의는 X좌표 차이와 Y좌표 차이 모두 1 이하일 경우로 정의된다.) 또한 산봉우리와 인접한 격자는 모두 산봉우리의 높이보다 작아야한다. 문제는 격자 내에 산봉우리의 개수가 총 몇 개인지 구하는 것이다.

입력

첫째 줄에 정수 N(1 < N ≤ 100), M(1 < M ≤ 70)이 주어진다. 둘째 줄부터 N+1번째 줄까지 각 줄마다 격자의 높이를 의미하는 M개의 정수가 입력된다. 격자의 높이는 500보다 작거나 같은 음이 아닌 정수이다.

출력

첫째 줄에 산봉우리의 개수를 출력한다.

예제

입력

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

출력

3

My Sol

import sys
input = sys.stdin.readline

def main():
    def find_heights():
        H = [set() for _ in range(501)]
        for i in range(I):
            for j in range(J):
                H[mat[i][j]].add((i, j))
        return H

    def check_around(i, j, h):
        if not (i, j) in H[mat[i][j]]: return
        H[mat[i][j]].remove((i, j))

        for di in range(-1, 2):
            si = i+di
            if not 0<=si<I: continue
            for dj in range(-1, 2):
                sj = j+dj
                if not 0<=sj<J: continue
                if mat[si][sj] > h: continue
                check_around(si, sj, mat[si][sj])
        return
        
    
    I, J = map(int, input().split())
    mat = [list(map(int, input().split())) for _ in range(I)]
    H = find_heights()
    cnt = 0
    while H:
        if not H[-1]:
            H.pop()
            continue
            
        while H[-1]:
            i, j = H[-1].pop()
            H[-1].add((i, j))
            check_around(i, j, mat[i][j])
            cnt += 1
    return cnt

print(main())          

그래프와 DFS를 활용하는 문제였다. 간단하게 해결할 수 있었다.

1. 가로, 세로, 높이 정보의 입력을 받는다.
2. 최대 높이는 500이므로, 길이가 501인 list에 set을 각각 넣어준다.
3. 높이 정보 mat 의 좌표별로 높이를 계산해 H 에 넣어준다.
4. 높은 봉우리부터 check_around 함수를 통해서 주변의 좌표를 확인한다. 높아지기 전까지 계속 반복하면 주변을 살핀다.
5. 이 과정에서 방문한 좌표는 H에서 제거한다. 이후에 봉우리로 인식하지 않기 위함이다.
6. check_around를 한 번 실행했다면 현재까지 중에 봉우리로 칠 수 있는 봉우리로부터 주변을 제거한 것이기 때문에 cnt를 1 올려준다.
7. 모든 mat의 좌표에 대해 이 과정을 실시한 뒤 cnt를 반환하여 출력한다.

결과

맞았습니다!!