(Python) - BOJ(2468번) : 안전 영역

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

2468번: 안전 영역

---

• 해설 : 

NxN 각 칸들의 높이가 주어지고, 비가 오는 높이가 주어질 때, 안전한 영역의 넓이가 최대가 되는 경우를 찾는 문제이다.

 

 

 

---

• 풀이 :

비가 1부터 가장 높은 높이의 건물만큼 오는 경우에 대해 BFS로 안전 영역의 개수를 카운트하고 MAX값을 갱신해주면 된다.

 

 

 

---

• 소스코드 : 

 

from collections import deque
N = int(input())
W = []
for _ in range(N):
    W.append(list(map(int,input().split())))
safe = []
#상 하 좌 우
dy = [0, 0 , -1, 1]
dx = [-1, 1, 0, 0]
 
def check_drown(i):
    for x in range(N):
        for y in range(N):
            if W[x][y] <= i:
                safe[x][y] = 1
 
def bfs(x,y):
    queue = [[x,y]]
    while queue:
        a, b = queue[0][0],queue[0][1]
        del queue[0]
        for k in range(4):
            x = a + dx[k]
            y = b + dy[k]
            if 0<= x < N and 0 <= y < N and safe[x][y] == 0:
                safe[x][y] = 1
                queue.append([x,y])
 
 
if __name__ == "__main__":
    m = 0
    for i in range(101):
        cnt = 0
        safe = [[0] * N for _ in range(N)]
        check_drown(i)
        for x in range(N):
            for y in range(N):
                if safe[x][y] == 0:
                    safe[x][y] = 1
                    bfs(x,y)
                    cnt+=1
 
        m = max(m,cnt)
print(m)