[백준] 6067 : Guarding the Farm (Python)

 

출처 : https://www.acmicpc.net/problem/6067

 

아이디어

해당 문제는 상하좌우 칸을 체크하며, 산봉우리에 포함되는 지역인지 확인해야하기 때문에 그래프 탐색 문제 유형으로 해석할 수 있다. 요구사항을 바탕으로, 어떻게 산봉우리 개수를 출력할지 생각해보자.

 

'인접하다'의 정의는 X좌표 차이와 Y좌표 차이가 모두 1이하인 경우

상하좌우뿐만 아니라, 대각선도 인접하다는 사실을 알 수 있다. 즉, 인접 칸(노드)들을 탐색하게 되는 간선이 8개가 존재한다.

 

산봉우리와 인접한 격자는 모두 산봉우리의 높이보다 작아야 한다.

산봉우리의 고도는 가장 커야 한다는 의미이다. 이를 통해, 산봉우리는 지역(덩어리)로 구분이 되고, 이에 따른 지역(덩어리) 개수를 출력해야하므로, BFS 탐색을 몇번 하는가를 정답으로 체킹하면 된다.

 

탐색 과정 설계

그렇다면, 어떤 식으로 탐색을 진행해야 할까? 경우의 수를 생각해보면 되는데, 이는 다음과 같다.

• 산봉우리(최고 고도)가 1개이고, 주변 지역 고도가 다 낮은 경우
• 산봉우리가 1개이고, 주변 지역 고도에 같은 최고 고도가 여러 개인 경우
• 산봉우리가 2개이고, 각 산봉우리의 주변 지역이 공유되는 경우

이들을 모두 아우르는 인사이트는 다음과 같다.

• 자신의 칸을 기준으로, 주변에 높은 고도가 있으면 BFS 탐색을 다음번으로 건너뛴다.
• 다시 말해, 최고 고도를 갖는 애들만을 덩어리 개수와 같다고 생각한다. 이에 따른 정답 카운팅 예시를 다음과 같이 첨부하였다.

 

산봉우리가 2개이고 각 산봉우리의 주변 지역이 공유하는 경우. 정답 카운팅 예시

 

즉, 주변에 높은 고도가 있는 경우는 False를 리턴하여 덩어리 개수를 갱신하지 않고, 주변에 높은 고도가 없어 정상적으로 자식 노드들을 다 방문한 경우는 True를 리턴하여 덩어리 개수를 갱신한다.

이를 바탕으로, BFS 탐색 개수를 카운팅하면 된다.

 

정답 코드

# https://www.acmicpc.net/problem/6067
# Guarding the Farm
# 그래프탐색, bfs

input=__import__('sys').stdin.readline
deque=__import__('collections').deque

def bfs(sx,sy):
    q=deque([(sx,sy)])
    visited[sx][sy]=1
    flag=True
    
    while q:
        x,y=q.popleft()
        for k in range(8):
            nx,ny=x+dx[k],y+dy[k]
            if 0<=nx<n and 0<=ny<m:
                if board[nx][ny]>board[x][y]:
                    flag=False
                if board[nx][ny]==board[x][y] and not visited[nx][ny]:
                    visited[nx][ny]=1
                    q.append((nx,ny))

    return flag
                    

n,m=map(int,input().split())
board=[[*map(int,input().split())] for _ in range(n)]
visited=[[0]*m for _ in range(n)]
dx=[0,0,-1,1,1,1,-1,-1]
dy=[-1,1,0,0,-1,1,-1,1]
answer=0

for i in range(n):
    for j in range(m):
        if board[i][j]>0 and not visited[i][j]:
            answer+=bfs(i,j)

print(answer)