1/10 Coding Test

✅ Coding Test

🎈 1245 농장 관리

농장의 크기는 NXM이고 이를 관리하기 위해 산봉우리마다 경비원을 배치하고자 한다. 이를 위해 농장에 산봉우리가 총 몇개 있는지 세는 것이 문제

산봉우리의 정의는 다음과 같다.

• 산봉우리는 같은 높이를 가진 하나의 격자 혹은 인접한 격자들의 집합으로 이루어져 있다. (인접한 케이스는 X좌표, Y좌표 차이 모두 1이라인 경우) 또한, 산봉우리와 인접한 격자는 모두 산봉우리 높이보다 작아야 한다.

from collections import deque
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
visited = [[False]*m for _ in range(n)]

# 방향 설정 12시부터 시계방향
dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, 1, 1, 1, 0, -1, -1, -1]
answer = 0

def bfs(i, j):
    global answer
    queue = deque([[i, j]])
    visited[i][j] = True
    result = True
    while queue:
        x, y = queue.popleft()
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<n and 0<=ny<m:
                if graph[nx][ny] > graph[x][y]:
                    result = False
                elif graph[nx][ny] == graph[x][y] and not visited[nx][ny]:
                    queue.append((nx, ny))
                    visited[nx][ny] = True
    if result:
        answer += 1

for i in range(n):
    for j in range(m):
        if not visited[i][j]:
            bfs(i, j)
print(answer)

< 해설 >
1. bfs함수를 통해 다음 과정을 거쳐 봉우리 여부를 확인한다.
1-1. 상하좌우대각선 총 8방향을 탐색해주어야 한다.
1-2. 주어진 범위 내 다음 위치의 높이가 지금보다 높다면 중단. (현재 위치가 봉우리가 아님)
1-3. 다음위치를 방문한 적이 없고 다음위치와 높이가 같다면 다음 위치를 queue에 넣고 방문처리
1-4. BFS 결과로 중단되지 않으면 answer + 1처리
2. 2중 for문을 돌고 방문한 적이 없는 칸에 한해 BFS탐색을 진행
3. 최종적으로 봉우리 개수 출력