1245 : 농장 관리 Python

접근

---

평범한 BFS 문제라고 생각했는데 조금 다른 부분이 있었다.

 

기존에 많이 풀어봤던 땅 문제들과 다르게 단순히 땅의 개수가 아닌 가장 높은 높이를 기준으로 땅을 세는 방식이다. 초반에 산봉우리와 인접한 격자는 모두 산봉우리의 높이보다 작아야 한다 이 부분을 잘못봐서 조금 헤멨다. 결국 생각해보니 특정 지점이 가장 높다면 산봉우리로 볼 수 있다는 것으로 해석이 가능하다.

 

그러려면 순차 탐색으로는 찾기 어려울 수 있다. 왜? 산봉우리라고 생각했던 지점이 실은 인접한 격자일 수 있기 때문이다. 그렇다면 '차라리 값을 기준으로 최대힙으로 저장해놓고, 이를 꺼내서 사용하는 방법은 어떨까?'하는 생각이 들었고 이 방향으로 진행했다.

 

여기서 "인접하다"의 정의는 X좌표 차이와 Y좌표 차이 모두 1 이하일 경우로 정의된다. 이부분도 잘못 이해했었다. 처음에는 두 좌표의 차이의 합 즉, 상하좌우만 가능하다고 생각했었는데 대각선도 가능이였다.

풀이

---

_map = []
for i in range(N):
    row = list(map(int, input().split()))
    for j in range(M):
        if not row[j]:
            continue
        heappush(heapq, (-row[j], i, j))
    _map.append(row)

핵심은 이 부분인 것 같다. 처음 값을 받을 때 높이가 0인 경우에는 산 봉우리가 될 수 없으므로 을 제외하고 높이를 최대힙에 저장한다. 이렇게 함으로써 최대힙에서 산봉우리 먼저 뺼 수 있다.

ans = 0
while heapq:
    val, r, c = heappop(heapq)
    if v[r][c]:
        continue
    BFS(r, c, -val)
    ans += 1

위에서 저장한 최대힙에서 산봉우리 후보를 뽑고, 이를 BFS를 돌려 산봉우리와 인접 격자를 모두 방문시킨다. 이후 산봉우리에 포함되지 않은 후보에 대해서만 BFS를 다시 수행한다.

전체 코드

---

import sys
from collections import deque
from heapq import heappush, heappop

# print = sys.stdout.write
input = sys.stdin.readline
# 반드시 아래 두 라인 주석 처리 후 제출
f = open("input.txt", "rt")
input = f.readline
# 반드시 위 두 라인 주석 처리 후 제출
DIRECTIONS = ((-1, -1), (-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1))

heapq = []
N, M = map(int, input().split())
_map = []
for i in range(N):
    row = list(map(int, input().split()))
    for j in range(M):
        if not row[j]:
            continue
        heappush(heapq, (-row[j], i, j))
    _map.append(row)

v = [[False] * M for _ in range(N)]

def BFS(r, c, val):
    q = deque([(r, c, val)])
    v[r][c] = True
    while q:
        y, x, value = q.popleft()

        for dy, dx in DIRECTIONS:
            ny, nx = dy + y, dx + x
            if (
                ny >= N
                or nx >= M
                or ny < 0
                or nx < 0
                or v[ny][nx]
                or not _map[ny][nx]
                or _map[ny][nx] > value
            ):
                continue

            q.append((ny, nx, _map[ny][nx]))
            v[ny][nx] = True

def main():
    ans = 0
    while heapq:
        val, r, c = heappop(heapq)
        if v[r][c]:
            continue
        BFS(r, c, -val)
        ans += 1
    print(ans)

if __name__ == "__main__":
    main()