[백준/BOJ] #1245 농장관리.python(파이썬)

문제 링크 / 출처

https://www.acmicpc.net/problem/1245

1245번: 농장 관리

 

문제 요약

산봉우리가 총 몇개인지 세는 문제

[제약사항]

• 1<N≤100
• 1<M≤70
• X좌표 차이와 Y좌표 차이 모두 1 이하일 경우 인접하다고 정의
• 산봉우리는 같은 높이를 가지는 하나의 격자 혹은 인접한 격자들의 집합으로 이루어져 있다.
• 산봉우리와 인접한 격자는 모두 산봉우리의 높이보다 작아야한다.

 

풀이

DFS를 이용해 인접한 동일 높이별로 그룹을 지어 탐색하도록 했다.

 

1. 현재위치와 동일한 높이를 가지는 격자들을 모두 방문한다.
   • 인접 격자에 현재 높이보다 낮은 격자들만 존재한다면 현재위치는 봉우리이고,
   • 인접 격자에 현재 높이보다 높은 격자가 하나라도 존재한다면 현재위치는 봉우리가 아니다.
2. 한번 탐색한 격자는 다시 탐색하지 않기 위해 방문체크를 해주었다.

 

코드

# 농장 관리

def is_top(r, c):   # 현재위치의 높이의 집합이 봉우리인지 확인
    now_height = farm[r][c]
    stack = [(r, c)]
    flag = True
    while stack:
        r, c = stack.pop()
        for dr, dc in drc:
            nr = r + dr
            nc = c + dc
            if 0 <= nr < N and 0 <= nc < M:
                if not visited[nr][nc] and farm[nr][nc] == now_height:
                    stack.append((nr, nc))  # 1. 인접한 동일 높이는 모두 탐색함
                    visited[nr][nc] = True  # 2. 방문체크
                elif farm[nr][nc] > now_height: # 1. 인접한 격자 중에 현재보다 높은 곳이 존재할 경우 봉우리가 아니다
                    flag = False    # 봉우리 체크

    if flag:
        return True

    return False


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

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

drc = [(0, -1), (-1, -1), (-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1)]
cnt = 0
stack = []

for r in range(N):
    for c in range(M):
        if not visited[r][c] and is_top(r, c):
            cnt += 1

print(cnt)