파이썬)안전영역 BOJ-2468

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

2468번: 안전 영역

 

from collections import deque

n = int(input())

max_area = 1

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

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


def bfs(arr, height):
    visit = [[False] * n for _ in range(n)]
    area = 0
    for i in range(len(arr[0])):
        for j in range(len(arr[0])):
            if visit[i][j] == False and arr[i][j] > height:
                visit[i][j] = True
                q = deque()
                q.append((i, j))

                while q:
                    x, y = q.popleft()

                    for p in range(4):
                        nx = dx[p] + x
                        ny = dy[p] + y

                        if 0 <= nx < n and 0 <= ny < n:
                            if visit[nx][ny] == False:
                                if arr[nx][ny] > height:
                                    q.append((nx, ny))
                                    visit[nx][ny] = True
                area += 1

    return area


for i in range(1, 100):
    area = bfs(arr, i)
    if area > max_area:
        max_area = area

print(max_area)

아주 조금만 생각하면 쉽게 풀 수 있는 문제이다.

우선 1부터 100까지 반복문으로 i를 강수량으로 설정했다.

bfs 함수를 99번 돌며 arr함수를 반복문으로 돌며 height(i)보다 작은 것이 있으면 bfs를 수행하고 카운트를 세준다.

즉, 어떤 영역의 넓이를 구하는데 최적화되어있는 bfs함수를 1부터 99까지 반복해주면 된다.