[백준 - Silver I] 안전 영역 - 2468

[백준 - Silver I] 안전 영역 - 2468

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

 

문제 설명

 

안전 영역이란 비에 잠기지 않은 지점들이 상하좌우로 존재하는 경우를 의미한다. 주어진 지도에서 물의 높이 H를 기준으로 안전영역의 개수를 계산하고, 이때 안전 영역이 최대가 되었을 때 영역 개수를 반환하는 것이 문제에서 요하는 출력값이다.

 

완전탐색으로 물 높이의 최소부터 최댓값까지 순회하며 이때 각 지역별로 정해진 높이가 h를 넘어가는 순간 BFS를 호출했다. 이때 BFS는 잠기지 않는 영역을 연결하고 BFS가 종료되면 안전영역의 카운트가 증가하는 방식으로 접근했다. 

 

그리고 이때의 최종 카운트가 기존의 answer를 넘어가는 순간 해당 cnt로 변경하므로 최대 영역 개수를 남겼다.

 

시간복잡도는 O(h×N^2)라고 생각했다. 각 강수량 별로 모든 지역을 탐색해야 하며 그렇기에 문제의 조건 2 <= N <= 100, 1 <= H <= 100에서는 총 100만 번의 계산이 발생한다. 그리고 이때 파이썬에서는 단순 연산 기준으로 초당 100만 회 처리 가능하므로 문제를 풀 때 해당 방법을 사용해도 괜찮을 것이라 판단했다.

 

풀이 코드

import sys
from collections import deque  # bfs를 위한 deque 선언

input = sys.stdin.readline
n = int(input())
area = [list(map(int, input().split())) for _ in range(n)]
answer = 0
minV, maxV = int(1e9), 0
for i in area:
    for j in i:
        if j < minV:
            minV = j
        if j > maxV:
            maxV = j

if minV == maxV : # 모든 지역의 높이가 동일한 경우 해당 지역은 잠기거나 잠기지 않거나
    print(1)
    exit()

def bfs(h, check, a, b):  # 높이, 시작 좌표값 입력
    dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    q = deque([(a, b)])
    check[a][b] = True
    while q: # 반복문의 종료는 해당 좌표에서 시작된 안전지역의 탐색 끝
        x, y = q.popleft()
        for dx, dy in dxy:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < n and 0 <= ny < n:
                if not check[nx][ny] and area[nx][ny] > h: # 안전지역만 체크 높이 이상의 지역만 순회
                    check[nx][ny] = True
                    q.append((nx, ny))
    return 1

for h in range(minV, maxV + 1):
    cnt = 0
    check = [[False] * n for _ in range(n)]

    for i in range(n):
        for j in range(n):
            if area[i][j] > h and not check[i][j]:
                cnt += bfs(h, check, i, j)
    if answer < cnt:
        answer = cnt

print(answer)