[백준] 1245번: 농장관리 - [Python/파이썬]

문제

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

1245번: 농장 관리

농부 민식이가 관리하는 농장은 N×M 격자로 이루어져 있다. 민식이는 농장을 관리하기 위해 산봉우리마다 경비원를 배치하려 한다. 이를 위해 농장에 산봉우리가 총 몇 개 있는지를 세는 것이 문제다.

산봉우리의 정의는 다음과 같다. 산봉우리는 같은 높이를 가지는 하나의 격자 혹은 인접한 격자들의 집합으로 이루어져 있다. (여기서 "인접하다"의 정의는 X좌표 차이와 Y좌표 차이 모두 1 이하일 경우로 정의된다.) 또한 산봉우리와 인접한 격자는 모두 산봉우리의 높이보다 작아야한다.

문제는 격자 내에 산봉우리의 개수가 총 몇 개인지 구하는 것이다.

입력

첫째 줄에 정수 N(1 < N ≤ 100), M(1 < M ≤ 70)이 주어진다. 둘째 줄부터 N+1번째 줄까지 각 줄마다 격자의 높이를 의미하는 M개의 정수가 입력된다. 격자의 높이는 500보다 작거나 같은 음이 아닌 정수이다.

출력

첫째 줄에 산봉우리의 개수를 출력한다.

코드

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

n, m=map(int, input().split())
data=[] 
for i in range(n):
    data.append(list(map(int, input().split())))

dx=[-1,-1,-1,0,0,1,1,1] 
dy=[-1,0,1,1,-1,-1,0,1]

checkidx=[]

def bfs(x, y, checkidx):
    q=deque([(x,y)])
    visited[x][y]=1
    check=[(x, y)]
    while q:
        X, Y= q.popleft()
        for i in range(8):
            nx, ny= X+dx[i], Y+dy[i] 
            if nx<0 or nx>=n or ny<0 or ny>=m:
                continue
            if visited[nx][ny]==1:
                continue
            if data[X][Y]<data[nx][ny]:
                return 0
            if data[X][Y]==data[nx][ny]:
                visited[nx][ny]=1
                q.append((nx,ny))
                check.append((nx,ny))
        checkidx+=check 
    return 1

tot=0
for i in range(n):
    for j in range(m):
        if (i, j) not in checkidx:
            visited=[[0]*m for _ in range(n)]
            tot+=bfs(i,j,checkidx)
print(tot)

문제해결

전형적인 그래프 이론 문제이다. BFS/DFS를 모두 활용할 수 있고, N,M의 크기가 크지 않으므로 모든 조건에 대해 DFS를돌려서 해결 할 수 있다.

필자는 BFS를 이용하여 문제를 해결하였다.

 현재 좌표 기준 8방향 좌표의 높이를 탐색하고, 한 번이라도 보다 더 높은 좌표가 발견된다면 해당 탐색은 산봉우리가 아닌 것으로 처리한다. 만일 같은 높이의 좌표가 발견된다면 큐에 넣고 탐색을 이어간다. 탐색 큐를 모두 살펴본 뒤 마지막에 산봉우리인지 아닌지에 대한 check배열을 확인하여 산봉우리의 개수를 추가해주면 된다. 당연하게도 무한루프에 빠질 수 있으니 방문 배열을 만들어 처리해야 한다.