[백준/python] 2468 - 안전 영역

2468번: 안전 영역

import sys
from collections import deque
sys.setrecursionlimit(10**6)

n = int(input())
city = []
max_height = 0
safe_zone = 0

def bfs(i, j, graph):
    global cnt
    q = deque()
    q.append((i, j))
    graph[i][j] = True
    while q:
        x_t, y_t = q.popleft()
        for dx, dy in (0, 1), (0, -1), (-1, 0), (1, 0):
            x, y = dx + x_t, dy + y_t
            if  0 <= x < n and 0 <= y < n and graph[x][y] == False and city[x][y] > height:
                    q.append((x, y))
                    graph[x][y] = True

for _ in range(n):
    input_arr = list(map(int, input().split()))
    target = max(input_arr)
    if target >= max_height:
        max_height = target
    city.append(input_arr)

for height in range(max_height + 1):
    graph = [[False] * n for _ in range(n)]
    cnt = 0
    for i in range(n):
        for j in range(n):
            if city[i][j] > height and graph[i][j] == False:
                bfs(i, j, graph)
                cnt += 1

    if cnt >= safe_zone:
        safe_zone = cnt

    cnt = 0

print(safe_zone)

| 알고리즘

• 첫번째 이중 for문을 돌면서 높이가 물의 높이보다 높고, 방문하지 않은 곳이라면 bfs로 들어간다.
• bfs로 들어가서 queue에 넣고 해당 좌표를 삽입한 뒤 방문 체크를 한다.
• queue가 다 빌 때까지 하나씩 leftpop한다.
• 그리고 해당 좌표의 동,서,남,북에서 물의 높이보다 높고, 방문하지 않은 곳이라면 queue에 넣고 방문 체크를 한다.
• 체크를 하다가 queue가 비면 bfs를 나와, cnt +=1를 해주고 다음 city 좌표를 탐색한다.

넘무 어려워요...