[백준/1245][Python] 농장 관리

문제

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

1245번: 농장 관리

풀이

BFS로 풀었다. 

우선 전체 배열을 탐색하며 방문한 적이 없다면 제일 높은 건지 확인하기 위해 해당 위치에서 BFS를 시작한다.

check라는 변수를 통해 인접 지역 중 해당 위치가 가장 높을지 안높을지 체크한다. 높으면 0, 안높으면 1을 반환했다.
큐에 해당 위치를 넣어주고, 8개를 돌며 인접한 곳을 모두 탐색하는데 이때 다음 탐색할 곳의 높이가 현재 위치의 높이보다 더 높다면, check를 1로 세팅해준다. check가 0으로 리턴되었다면 현재 위치보다 더 높은게 없는 것을 뜻한다. 

vis의 검사 또한 높은게 있나 확인을 먼저 한 다음에 해줘야한다. 일단 주위를 다 둘러보고 높은게 있나 확인하고 값이 같은게 존재하면 그 주위를 또 둘러보는 식으로 코드가 진행되기 때문이다.

코드

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

n,m = map(int,read().split())
board = [list(map(int,read().split())) for _ in range(n)]

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

vis = [[0]*m for _ in range(n)]
def check_top(i,j):
  check = 0 #젤 높을지 안높을지 체크할 변수
  dq = deque()
  dq.append((i,j))
  vis[i][j] = 1
  while(dq):
    x,y = dq.popleft()
    for dir in range(8):
      nx = x + dx[dir]
      ny = y + dy[dir]
      if nx<0 or ny<0 or nx>=n or ny>=m:
        continue
      if board[x][y]<board[nx][ny]: #현재 위치보다 더 높은게 나오면 check를 1로 세팅
        check = 1
      if vis[nx][ny] == 0 and board[x][y]==board[nx][ny]:
        vis[nx][ny] = 1
        dq.append((nx,ny))
  return check #0이 리턴되면 현재 위치보다 더 높은게 없는 거임           

ans = 0
for i in range(n):
  for j in range(m):
    if not vis[i][j]:
      #방문한 적이 없다면 제일 높은 건지 확인해 줘야함
      if check_top(i,j) == 0:
        ans += 1
print(ans)