[BOJ / PYTHON] 2468 - 안전 영역

from sys import stdin
from collections import deque

input = stdin.readline

N = int(input())

arr = list(list(map(int, input().split())) for _ in range(N))

lands = 0

def bfs(s, e):
    global N
    q = deque()
    q.append((s, e))

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

    while q:
        y, x = q.popleft()

        for i in range(4):
            ny, nx = y + dy[i], x + dx[i]

            if 0 <= ny < N and 0 <= nx < N and not visited[ny][nx] and land[ny][nx]:
                q.append((ny, nx))
                visited[ny][nx] = True

    return True


for i in range(0, 100):

    land = list([False] * N for _ in range(N))
    visited = list([False] * N for _ in range(N))

    for y in range(N):
        for x in range(N):
            if arr[y][x] > i:
                land[y][x] = True

    cnt = 0
    for y in range(N):
        for x in range(N):
            if not visited[y][x] and land[y][x]:
                bfs(y, x)
                cnt += 1
    lands = max(lands, cnt)

    if cnt == 0:
        break

print(lands)

풀이.

비가 내렸을 때 잠기지 않은 땅의 갯수를 세는 것이다.
땅은 상하좌우로 이어진 경우 하나로 본다.

모든 땅이 잠기지 않을 경우 하나의 섬으로 본다고 생각하면 된다.

가장 많은 섬이 생기는 경우를 출력하는 것이 답이다.

우선, 비에 잠긴 것을 확인 할 수 있는 배열을 만들고, 해당 배열을 (1, 1) 부터 (N, N) 까지 BFS 탐색 하여 BFS 탐색이 이뤄진 횟수가 섬의 갯수이다.