[BOJ]2468 안전영역 파이썬 풀이

[백준] 안전 영역 (2468) - BFS

문제 링크: https://www.acmicpc.net/problem/2468

문제 요약

• N x N 크기의 지역이 있다.
• 각 지역의 높이는 1 이상 100 이하의 자연수이다.
• 비가 내리면 높이가 같거나 낮은 지역은 물에 잠긴다.
• 물에 잠기지 않는 안전한 영역의 개수를 구하라.

[위 문제 요약은 chat-gpt를 이용하였습니다.]

import copy
from collections import deque
n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]
max_height = max(map(max, graph))

def run(graph, visited, i, j):
    visited[i][j] = 1

    q = deque()
    q.append([i, j])
    dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
    while q:
        cx, cy = q.popleft()
        for i in range(4):
            nx, ny = cx + dx[i], cy + dy[i]
            if 0 <= nx < n and 0 <= ny < n:
                if graph[nx][ny] != 0 and not visited[nx][ny]:
                    q.append([nx, ny])
                    visited[nx][ny] = 1


def bfs(g, rain):
    graph = copy.deepcopy(g)
    visited = [[0 for _ in range(n)] for __ in range(n)]
    depth = 0

    for i in range(len(graph)):
        for j in range(len(graph[i])):
            graph[i][j] = graph[i][j] - rain \
                if graph[i][j] >= rain else 0

    for i in range(len(graph)):
        for j in range(len(graph[i])):
            if graph[i][j] > 0 and not visited[i][j]:
                depth += 1
                run(graph, visited, i, j)

    return depth
            

area = 0
for rain in range(0, max_height):
    area = max(area, bfs(graph, rain))
print(area)