[백준/ 파이썬] 2468번 안전 영역

백준 2468 안전 영역 BFS

최근에 BFS DFS 문제를 열심히 풀고 있다.
기존의 비교적 쉬운 문제들에서는 영역을 구하는데에 있어 가지말아야할 곳이 지정되어 문제를 풀게 되어있었다. 이 문제는 가지못하는 모든 경우를 직접 구해야했다.

안전한 영역은 내리는 비의 양에 따라 달라질 것이다.

그렇다면 내리는 비의 양은 0~100까지 모두 구해야 할까?
아니다. 우리는 지역의 높이들 중에서 가장 작은 높이와 가장 큰 높이를 구해서 해당 범위 안에서 안전한 영역의 수를 구하면 된다.

여기서 조심해야할 점은 가장 작은 높이에서 시작하면 안된다.
Why? 만약 모든 지역의 높이가 2라고 가정한다면. 2에서 시작할 경우 안전한 영역은 없다고 나올것이다. 따라서 우리는 (가장 작은 높이 - 1)부터 시작을 해야할 것이다.

정답

from collections import deque

def bfs(x,y, rainLevel):
    queue = deque()
    queue.append((x,y))

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or nx >= n or ny < 0 or ny >= n:
                continue

            if matrix[nx][ny] <= rainLevel or visited[nx][ny] == 1:
                continue
            else:
                queue.append((nx, ny))
                visited[nx][ny] = 1

    return 1


n = int(input())
matrix = []
minLevel = 101
maxLevel = 0
for _ in range(n):
    x = list(map(int, input().split()))
    minLevel = min(minLevel, min(x))
    maxLevel = max(maxLevel, max(x))
    matrix.append(x)

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

area = 0
answer = 0
minLevel -= 1
while minLevel < maxLevel:
    visited = [[0]*n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if matrix[i][j] > minLevel and visited[i][j] == 0:
                area += bfs(i, j, minLevel)
    answer = max(answer, area)
    area = 0
    minLevel += 1

print(answer)