[boj] 백준 2468 안전 영역 python 풀이(bfs)

문제

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

2468번: 안전 영역

 

문제 풀이

비가 올 수 있는 모든 경우에 대해서, 비(height) 높이를 초과하는 높이의 영역의 갯수 bfs로 찾기. 섬 갯수 찾기 bfs 문제와 유사함. 
유니온 파인드로 푸는게 훨씬 효율적,, 나는 뇌가 bfs에 절여진듯,,
 

코드

import sys
input = sys.stdin.readline
import collections

N = int(input().strip())
MAP = [list(map(int,input().split())) for _ in range(N)]
MAX_HEIGHT = max(map(max,MAP))
MAX_AREA_CNT = 1

def find_area(MAP, height):
    visited = [[0 for _ in range(N)] for _ in range(N)]
    cnt = 0

    for i in range(N):
        for j in range(N):
            if visited[i][j] == 0 and MAP[i][j]>height:
                bfs(MAP, i, j, visited, height)
                cnt += 1

    return cnt

def bfs(MAP, i, j, visited, height):
    move = {(-1,0),(0,1),(1,0),(0,-1)}
    q = collections.deque()
    q.append((i,j))

    visited[i][j] = 1
    
    while q:
        x,y = q.popleft()

        for tx, ty in move:
            nx = tx + x
            ny = ty + y

            if 0<=nx<N and 0<=ny<N and visited[nx][ny] == 0 and MAP[nx][ny] > height:
                q.append((nx,ny))
                visited[nx][ny] = 1


for i in range(1, MAX_HEIGHT):
    MAX_AREA_CNT = max(MAX_AREA_CNT, find_area(MAP, i))

print(MAX_AREA_CNT)