백준 1245(농장 관리) - 해결

농장 관리

 

문제

농부 민식이가 관리하는 농장은 N×M 격자로 이루어져 있다. 민식이는 농장을 관리하기 위해 산봉우리마다 경비원를 배치하려 한다. 이를 위해 농장에 산봉우리가 총 몇 개 있는지를 세는 것이 문제다.

산봉우리의 정의는 다음과 같다. 산봉우리는 같은 높이를 가지는 하나의 격자 혹은 인접한 격자들의 집합으로 이루어져 있다. (여기서 "인접하다"의 정의는 X좌표 차이와 Y좌표 차이 모두 1 이하일 경우로 정의된다.) 또한 산봉우리와 인접한 격자는 모두 산봉우리의 높이보다 작아야한다.

문제는 격자 내에 산봉우리의 개수가 총 몇 개인지 구하는 것이다.

 

입력

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

 

출력

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

---

처음에 어떻게 할지 고민하였다.

가장 높은 걸 찾아야하고 이와 같은 높이를 같은 산봉우리로 치는 것.

그래서 생각한 것은 현재 높이와 같은 것은 저장하면서 탐색을 하고 탐색중 인접한 곳에 더 높은 곳이 있으며 0을 리턴하고 아니라면 1을 리턴하여 산봉우리의 갯수를 파악하였다.

import sys
input = sys.stdin.readline
N, M = map(int,input().split())

dirs = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

maps = [list(map(int,input().split())) for _ in range(N)]

visit = [[0] * M for _ in range(N)]

# 탐색
def dfs(i,j):
    q = [(i,j)]
    # 산봉우리면 1을 리턴하기 위해
    ans = 1
    # 높이 저장
    n = maps[i][j]

    while q:
        x, y = q.pop()

        visit[x][y] = 1

        for i in range(8):
            nx = x + dirs[i][0]
            ny = y + dirs[i][1]
            # 범위 파악
            if 0 <= nx < N and 0 <= ny < M:
                # 방문하지 않고 높이가 같으면 같은 봉우리이기 때문에 여기서도 탐색
                if maps[nx][ny] == n and visit[nx][ny] == 0:
                    q.append((nx,ny))
                # 만약 탐색중 더 높은 봉우리가 있다면 산봉우리가 아님
                elif maps[nx][ny] > n:
                    ans = 0
    return ans

# 결과
result = 0

# 전체를 탐색
for i in range(N):
    for j in range(M):
        # 방문하지 않았고 0 이상인 부분에서만 탐색
        if visit[i][j] == 0 and maps[i][j]:
            result += dfs(i,j)

print(result)