백준 2468: 안전 영역 Python

 

https://www.acmicpc.net/problem/2468

2468번: 안전 영역

 

 

높이가 1이상 100 이하의 정수인데, 1~100까지의 높이 모두를 고려하는 것은 시간 낭비이다.

따라서 가장 먼저 2차원 배열에 있는 값 중 가장 큰 값(=최대 높이)을 찾는다.

그리고 0부터 최대높이까지 각 높이에 대해 물에 잠기는 경우를 고려한다.

 

from collections import deque
import sys
input = sys.stdin.readline


def bfs(si, sj, num):
    q = deque()
    q.append((si, sj))
    visited[si][sj] = 1

    while q:
        si, sj = q.popleft()
        for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            ni, nj = si+di, sj+dj
            if 0 <= ni < N and 0 <= nj < N and land[ni][nj] > num and not visited[ni][nj]:
                visited[ni][nj] = 1
                q.append((ni, nj))


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

# 2차원 배열의 최대값(=최대 높이)을 구한다
max_land = 0
for i in range(N):
    max_land = max(max_land, max(land[i]))

# 각 높이에 대해 잠겼을 경우를 고려
result = 0
for n in range(max_land):
    visited = [[0] * N for _ in range(N)]
    count = 0
    for i in range(N):
        for j in range(N):
            if land[i][j] > n and not visited[i][j]:
                bfs(i, j, n)
                count += 1
    result = max(result, count)
print(result)