백준 2468 안전 영역

과정

• 빗물의 높이 별로 안전 영역의 개수를 구하기
• bfs로 안전 영역 덩어리를 구했다.
• 안전 영역의 개수 최대인 경우를 저장해서 출력하기.
• 빗물의 높이는 최대 100이다 -> 입력 잘 확인하기

import sys
from collections import deque

input = sys.stdin.readline

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

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


def bfs(x, y, height, visited):
    queue = deque([(x, y)])
    while queue:
        a = queue.popleft()
        x = a[0]
        y = a[1]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < N and not visited[ny][nx] and map_lst[ny][nx] >= height:
                visited[ny][nx] = True
                queue.append((nx, ny))
    return visited


max = 0
for height in range(101):
    cnt = 0
    visited = [[False] * N for _ in range(N)]
    for j in range(N):
        for i in range(N):
            if map_lst[j][i] >= height and not visited[j][i]:
                visited[j][i] = True
                visited = bfs(i, j, height, visited)
                cnt += 1
    if max < cnt:
        max = cnt
        
print(max)

• bfs에서 queue에 append를 x, y 해줘서 한참 헤매고 있었다. 익숙하다고 방심하면 실수하므로 조심하기.