[Python] 백준2468번 : 안전 영역

💡문제

백준 2468번 문제 링크

🍀풀이

문제를 보고 저번에 풀었던게 생각이 났다.

1. 받은 높이 정보에서 최대 높이 저장
2. 최대 높이까지 하나씩 bfs 돌려서 최대 개수 구하기
3. 이때, graph의 현재 높이가 지금 돌려는 높이보다 클 때만 bfs 돌리기 (물에 안잠기는 높이만)

이런식으로 생각을 해서 풀었다.

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

n = int(input().strip())

graph = []
maxNum = 0
result = 0

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

for _ in range(n):
    arr = list(map(int, input().split()))
    if max(arr) > maxNum:	# 최대 높이 구하기
        maxNum = max(arr)
    graph.append(arr)

def bfs(x, y, z):
    queue = deque()
    queue.append((x, y))
    visited[x][y] = 1
    
    while queue:
        x, y = queue.popleft()
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n and visited[nx][ny] == 0 and graph[nx][ny] > z:		# 물에 잠기지 않는 지점만
                queue.append((nx, ny))
                visited[nx][ny] = 1
        
for h in range(0, maxNum+1):
    visited = [[0] * n for _ in range(n)]
    num = 0
    for i in range(n):
        for j in range(n):
            if visited[i][j] == 0 and graph[i][j] > h:
                bfs(i, j, h)
                num += 1
    result = max(result, num)

print(result)

최대 개수를 어디서 세어야할지 살짝 헷갈려서 좀 헤맸는데 어찌저찌 잘 해결했다.