[BOJ] 1245. 농장 관리 (🥇, BFS)

🔗

풀이

봉우리의 조건은 다음과 같다.

가로와 세로가 각각 1이하 거리에 있는 같은 높이의 값
인접한 모든 값들이 다 현재 봉우리의 높이보다 낮은 높이인 경우

그림에서 하늘색은 인접한 높이를 가진 인접한 격자들을 묶은 것이다.

위의 경우는 주변에 높이 3이 있기 때문에 봉우리가 될 수 없다. 하지만 밑의 경우는 주변에 0과 1밖에 없기 때문에 봉우리가 될 수 있다.

이 문제의 핵심은 같은 높이의 인접한 격자들을 찾고, 인접한 격자 중 더 높은 높이를 갖는 경우를 탐색하는 그래프 탐색이다. 너비 우선 탐색으로 진행했으며, 같은 높이를 갖는 경우 큐에 넣고 탐색을 진행하고, 더 높은 높이를 탐색하는 경우 flag에 False값을 넣었다. 최종적으로 봉우리의 개수를 세어야 하기 때문에 flag값을 반환하고 반환된 값을 cnt에 더하는 식으로 개수를 셌다.

인접한 값 탐색 중 더 높은 높이를 찾는 경우는 방문처리된 값에 상관없이 찾아야 하기 때문에 이 부분을 주의해야 한다.

# 농장 관리

def bfs(_i, _j, x):
    flag = True
    visited[_i][_j] = True
    queue = [(_i, _j)]
    while queue:
        i, j = queue.pop(0)
        for di, dj in dij:
            ni, nj = i+di, j+dj 
            if -1<ni<N and -1<nj<M:
                if arr[ni][nj] > arr[i][j]:
                    flag = False
                elif not visited[ni][nj] and arr[ni][nj] == x:
                    visited[ni][nj] = True
                    queue.append((ni, nj))
    return flag

N, M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
visited = [[False]*M for _ in range(N)]
dij = [(-1, 0), (0, 1), (1, 0), (0, -1), (1, 1), (1, -1), (-1, 1), (-1, -1)]

cnt = 0 
for i in range(N):
    for j in range(M):
        if not visited[i][j]:
            cnt += bfs(i, j, arr[i][j])
print(cnt)