BOJ - 안전 영역(2468)

실버1 : BFS 문제이다.

풀이

물의 높이를 존재하는 min값에서 max로 잡아줬었는데, 이렇게 하지않고 0부터 하니 통과했다. 국어문제인듯한데.. 아무래도 비가 안오는 것부터 체크해주는게 보다 맞는 것 같긴하다.

Code

# 안전영역 최대 개수
# visited -> 할때마다 초기화
# BFS 함수
 
 
import sys
from collections import deque
from itertools import chain
from pprint import pprint
 
 
def BFS(y, x):
    global n, visited
    q = deque()
    q.append([y, x])
    visited[y][x] = 1
    d = [[1, 0], [0, 1], [-1, 0], [0, -1]]
    while q:
        cy, cx = q.pop()
 
        for dy, dx in d:
            ny, nx = cy + dy, cx + dx
            if 0 <= ny < n and 0 <= nx < n and visited[ny][nx] == 0:
                visited[ny][nx] = 1
                q.append([ny, nx])
 
 
input = sys.stdin.readline
 
n = int(input())
pool = []
for _ in range(n):
    pool.append(list(map(int, input().split())))
low, high = 0, max(chain(*pool))
 
answer = 0
for height in range(low, high + 1):
    visited = [[0 for _ in range(n)] for _ in range(n)]
    safe_area = 0
    for i in range(n):
        for j in range(n):
            if pool[i][j] <= height:
                visited[i][j] = -1
    for i in range(n):
        for j in range(n):
            if visited[i][j] == 0:
                BFS(i, j)
                safe_area += 1
    answer = max(answer, safe_area)
 
print(answer)

Reference

• 백준(2468번) - 안전 영역