백준 2468 python [안전 영역]

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

import sys
from collections import deque

# with open('./data.txt', 'r') as file:
#     lines = file.read().strip().split('\n')
    
# N = int(lines[0])
N = int(sys.stdin.readline())

moveX = [1, 0, -1, 0]
moveY = [0, -1, 0, 1]
graph = [[0] * N for _ in range(N)]

# 그래프 그리기
for i in range(N):
    # arr = list(map(int, lines[i+1].split()))
    arr = list(map(int, input().split()))
    for k in range(N):
        graph[i][k] = arr[k]
        
def bfs(x, y):
    Q = deque()
    Q.append((x, y))
    visited[x][y] = True
    
    while Q:
        a, b = Q.popleft()
        
        for i in range(4):
            nextX = a + moveX[i]
            nextY = b + moveY[i]

            # 범위를 벗어났거나 물에 잠긴 경우 스킵
            if(nextX >= N or nextY >= N or nextX < 0 or nextY < 0):
                continue
            
            if(visited[nextX][nextY] == True or graph[nextX][nextY] <= r):
                continue

            visited[nextX][nextY] = True
            Q.append((nextX, nextY))

# 그래프에서 최고 높이 값
maxRegion = max(map(max, graph))
counts = []

for r in range(maxRegion+1):
    visited = [[False] * N for _ in range(N)]
    cnt = 0

    for i in range(N): #행
        for k in range(N):  #열
            if(graph[i][k] > r and not visited[i][k]):
                bfs(i, k)
                cnt += 1
    
    counts.append(cnt)

print(max(counts))

접근 방법

많이 막막했지만 막상 또 풀고나면 간단한 원리의 문제였다.

해당 문제는 빗물의 양을 모르는 상태에서 안전지역의 개수를 구하는게 키 포인트였던 것 같다. 즉 파라미터를 모를 때.

처음에는 1부터 100까지 모든 빗물을 확인해야하나? 생각했지만 어차피 빗물이 지도의 최고 높이를 초과한다면
안전지역은 없기 때문에 0부터 그래프 최고 높이까지만 확인 하면 됐었다.

다른 문제처럼 bfs를 돌리면서 개수를 구하지만
지도 내 최고 높이값만큼 반복문을 돌면서 개수를 다시 구하면 된다.