[백준] 2468 안전영역 BFS

from collections import deque

n = int(input())

arr = [list(map(int, input().split())) for _ in range(n)]

def bfs(i,j,k,visited):

    q=deque()

    q.append([i,j])

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

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

    while q:

        y,x = q.popleft()

        visited[y][x] = True

        for i in range(4):

            y_=y+dy[i]

            x_=x+dx[i]

            if 0<=y_<n and 0<=x_<n and not visited[y_][x_] and arr[y_][x_]>k:

                visited[y_][x_]=True

                q.append([y_,x_])

max_height = max(max(row) for row in arr)

m = 0

for k in range(max_height + 1):

    visited = [[False for _ in range(n)] for _ in range(n)]

    cnt = 0

    for i in range(n):

        for j in range(n):

            if arr[i][j] > k and not visited[i][j]:

                bfs(i, j, k, visited)

                cnt += 1

    m = max(cnt, m)

print(m)

 

오 VSCODE 그냥 복붙했더니 그대로 색상 반영되네 신기하다

 

빙산보다 쉽고 그림보다 어려운 문제

모든 BFS는 그림을 응용할 수 있다... 그림은 사실 GOAT 문제인게 아닐까

 

가장 높은 높이를 구해서, 0부터 가장 높은 높이까지 1씩 높여가면서

각 침수 높이에서 안전 영역 땅덩어리가 몇개 나오는지 구하자

 

초기화 주기는, 빗물 높이가 바뀔 때마다 visited, cnt 초기화

각 빗물 높이마다 이중 for문을 돌며, 빗물 높이보다 높고, 방문하지 않은 node에 대해 bfs를 수행한다

bfs가 수행될 때마다, 해당 영역과 연결된 빗물높이보다 높은 node는 모두 visit 처리됐을거니까 땅덩어리 개수+1해줌

 

그럼 이중 for문이 끝나면 해당 빗물 높이에서 안전영역 총 개수가 나옴

m 변수랑  max 비교해서 더 큰 값이면 최댓값 갱신

 

다 끝나면 m 반환

 

근데 3중 for문에 bfs 함수 내부에서 while문까지 돌려서

거의 n^3logn인데 이게 맞나 싶다