[백준] 2468번, 안전영역 (Python)

문제

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

2468번: 안전 영역

 

코드

import collections

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

def bfs(x, y, k):
    queue = collections.deque()
    queue.append((x,y))
    count = 1
    dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
    while queue:
        x, y = queue.popleft()
        check[x][y] = True
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n:
                if graph[nx][ny] > k and check[nx][ny] == False:
                    queue.append((nx,ny))
                    check[nx][ny] = True
                    count += 1
    return count

# 입력값중에 가장 큰값을 구해준다.
curMax = 0
for i in range(n):
    for j in range(n):
        curMax = max(curMax, graph[i][j])

lenCurMax = 0
# 비의 범위는 가장 높은 건물의 크기만큼으로 정해준다
for k in range(curMax+1):
    check = [[False] * n for _ in range(n)]
    result = []
    for x in range(n):
        for y in range(n):
            if graph[x][y] > k and check[x][y] == False:
                result.append(bfs(x,y,k))
    lenCurMax = max(lenCurMax, len(result))
    
print(lenCurMax)

내리는 비의 양에 따라 안전한 영역의 최대 갯수를 구하는 문제이다.

 

bfs를 실행할때 비의양도 k도 포함해 bfs를 실행한다

graph에 값이 k보다 크다면 안전영역이므로 bfs안에서 건물의 갯수를 count를 세어주는데 결과값으로는 필요한 값은 아니다.

 

결과값은 안전한 영역의 갯수이기 때문에 영역안에 건물에 갯수는 중요하지않고 bfs 호출횟수를 result배열 길이로 나타낼 수 있으므로 result에 길이가 가장 큰 값이 안전한 영역의 최대 갯수가 된다.