백준 - 안전 영역 / Silver 1 / 2468번 / Python

문제 📋

백준 - 안전 영역

풀이 📝

import sys
from collections import deque


def bfs(area, start, criteria):
    global visited
    q = deque([start])
    n = len(area)

    ways = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    while q:
        row, col = q.popleft()

        for way in ways:
            delta_row, delta_col = way

            next_row = row + delta_row
            next_col = col + delta_col

            if next_row < 0 or next_row >= n or next_col < 0 or next_col >= n:
                continue
            if visited[next_row][next_col]:
                continue

            if area[next_row][next_col] > criteria:
                q.append((next_row, next_col))
                visited[next_row][next_col] = True


def solution(N, area):
    answer = []
    global visited

    for criteria in range(0, 101):
        cnt = 0
        visited = [[False] * N for _ in range(N)]

        for i in range(N):
            for j in range(N):
                if not visited[i][j] and area[i][j] > criteria:
                    bfs(area, (i, j), criteria)
                    cnt += 1
        answer.append(cnt)
    return max(answer)


N = int(sys.stdin.readline())
area = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
global visited

print(solution(N, area))

빗물에 잠긴 지역을 제외한 안전 영역의 개수 중 최대치를 찾아내는 문제이다.
DFS로 탐색하든 BFS로 하든 크게 상관은 없다고 생각한다.

빗물의 높이를 기준으로 삼고 탐색할 때 기준을 입력받아서 탐색을 진행해야 한다.
영역의 개수를 측정하는 것은 BFS 탐색을 진행할 때마다 카운팅 해주면 된다.