문제 설명

농장 관리 문제의 링크는 아래에.
1245번: 농장 관리

NxM 크기로 이루어진 2차원 공간 각각의 0~500 사이의 값이 주어진다.
이때 인접한 구역 보다 큰 값을 가지는 구역(이하 봉우리)의 개수를 구해서 반환하면 된다.

접근

특정 구역이 봉우리인지 여부를 판단하기 위해서는
1)인접한 같은 값을 가진 구역을 찾아
2)각 구역의 인접한 구역 중 자신보다 큰 값을 가진 곳이 있는지 확인해야 한다.

따라서 탐색 알고리즘을 사용해야하는데, 나의 경우 BFS를 사용했다.

# 모든 구역에 대해 탐색 시작
for n in range(N):
    for m in range(M):
		
        # 이미 탐색한 곳이면 패스
        if visited[n][m]:
            continue
		
        # 연결된 같은 값을 지닌 구역을 찾기 위해 BFS 사용
        queue = deque([(n, m)])
        # 봉우리 여부
        flag = True

        while queue:
            y, x = queue.pop()
            visited[y][x] = True
            
            for dy, dx in D:
                if y+dy>=0 and y+dy<N and x+dx>=0 and x+dx<M:
                   # 현재 구역과 같은 값이고 미탐색한 곳이면 이어서 탐색
                   if A[y][x] == A[y+dy][x+dx] and not visited[y+dy][x+dx]:
                        queue.append((y+dy, x+dx))
                   # 탐색중에 인접한 구역 중 더 큰 구역을 찾으면 봉우리 X
                   elif A[y][x] < A[y+dy][x+dx]:
                        flag = False
		
        if flag:
            answer += 1

소스코드

최종적으로 제출한 코드는 다음과 같다.

# 농장 관리 : 골드 5
from collections import deque
import sys
input = sys.stdin.readline

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

answer = 0
visited = [[False for m in range(M)] for n in range(N)]
D = [(0, -1), (0, 1), (-1, -1), (1, -1), (-1, 0), (1, 0), (1, 1), (-1, 1)]

for n in range(N):
    for m in range(M):

        if visited[n][m]:
            continue

        queue = deque([(n, m)])
        flag = True

        while queue:
            y, x = queue.pop()
            visited[y][x] = True
            
            for dy, dx in D:
                if y+dy>=0 and y+dy<N and x+dx>=0 and x+dx<M:
                    if A[y][x] == A[y+dy][x+dx] and not visited[y+dy][x+dx]:
                        queue.append((y+dy, x+dx))
                    elif A[y][x] < A[y+dy][x+dx]:
                        flag = False

        if flag:
            answer += 1

print(answer)

결과

회고

예전에 많이 풀어봤던 유형임에도 불구하고 오랜만에 구현하니까 생각보다는 오래 걸렸다.
꾸준히 알고리즘을 해야겠다는 생각이 다시 한 번 들었다.