8. [re] 안전 영역

아현·2021년 10월 5일
0

Algorithm

목록 보기
330/400

백준




1. BFS


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

n = int(input())
height = [list(map(int, input().split())) for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(x, y, h):
    q = deque()
    q.append((x,y))
    while q:
        x,y = q.pop()
        for i in range(0, 4):
            nx = x + dx[i]
            ny= y + dy[i]
            if 0 <= nx < n and 0 <= ny < n:
                if(visit[nx][ny] == 0 and height[nx][ny] > h):
                    visit[nx][ny]=1
                    q.append((nx,ny))


cnt = 0
for h in range(max(map(max, height))):
    keep = 0
    visit = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if visit[i][j] == 0 and height[i][j] > h:
                visit[i][j]=1
                bfs(i, j, h)
                keep += 1
    if keep > cnt:
        cnt = keep

print(cnt)
profile
For the sake of someone who studies computer science

0개의 댓글