baekjoon 2468: 안전영역

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

2468번: 안전 영역

 

비가올때 장마철 물에 잠기지 않는 안전한 영역의 최대 개수를 출력하는 문제이다.

2차원 배열의 숫자들은 건물의 높이를 의미하고, 건물들의 군집?의 갯수들을 확인하여 최다군집을 구하면 된다.

 

비가 하나도 안왔을시, 건물군집은 1이되고 비가 건물의 최대높이까지 왔을시 건물군집은 0이된다.

 

난 flood fill 알고리즘을 이용하여, 비가 0만큼 내렸을때부터 건물최대높이까지 내렸을때까지 result라는 빈배열에 건물군집의 갯수를 넣었고, 그 result라는 배열의 max값을 도출하는 식을 사용하였다.

 

아래는 내가 작성한 코드!

from collections import deque
import copy
n = int(input())
arr = [list(map(int,input().split()))for _ in range(n)]
backup = copy.deepcopy(arr)
Max = -1
result = []
for y in range(len(arr)):
    for x in range(len(arr[y])):
        Max = max(Max,arr[y][x])

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

    while q:
        directy = [-1, 1, 0, 0]
        directx = [0, 0, -1, 1]
        nowy,nowx = q.popleft()
        for i in range(4):
            dy = directy[i]+nowy
            dx = directx[i]+nowx
            if 0<=dy<n and 0<=dx<n:
                if arr[dy][dx] == 0: continue
                arr[dy][dx] = 0
                q.append((dy,dx))

for i in range(Max):
    cnt = 0
    arr = copy.deepcopy(backup)
    for y in range(len(arr)):
        for x in range(len(arr[y])):
            if arr[y][x] <= i:
                arr[y][x] = 0

    for y in range(len(arr)):
        for x in range(len(arr[y])):
            if arr[y][x] >= 1:
                arr[y][x] = 0
                bfs(y,x)
                cnt+=1
    result.append(cnt)
print(max(result))