[python] 백준 2468 안전 영역

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

2468번: 안전 영역

 

문제 해결

•  문제를 이해하는 것 부터 어렵다.
•  물에 잠기는 높이는 정해지지 않았다. 물의 높이가 i일 때 잠기지 않는 영역의 개수를 구할 수 있다.
•  물의 높이를 바꿔가며 잠기지 않는 영역의 최대 개수를 구하는 것이다.
•  물의 높이는 0부터 (가장 높은 지역 -1) 까지 차례로 고정하고 문제를 해결할 것이다.
•  영역의 개수를 구하는 것은 bfs()의 단골 문제이다. visited를 이용해서 영역의 개수를 구하면 된다.

 

CODE

from collections import deque

n = int(input())
graph = []
maxNum = 0 

for i in range(n):
    graph.append(list(map(int, input().split())))
    for j in range(n):
        if graph[i][j] > maxNum:
            maxNum = graph[i][j]

move = ((1,0), (-1,0), (0,1), (0,-1))

def bfs(a,b,value,visited):
    que = deque()
    que.append((a,b))
    visited[a][b] = 1

    while que:
        x, y = que.popleft()
        for next in move:
            new_x = x + next[0]
            new_y = y + next[1]
            if 0<=new_x<n and 0<=new_y<n:
                if graph[new_x][new_y] > value and visited[new_x][new_y] ==0:
                    visited[new_x][new_y] = 1
                    que.append((new_x,new_y))
ans = 0
for i in range(maxNum):
    visited = [[0 for _ in range(n)] for _ in range(n)]
    cnt = 0
    for j in range(n):
        for k in range(n):
            if graph[j][k] > i and visited[j][k] ==0:
                bfs(j,k,i,visited)
                cnt += 1
    if ans < cnt:
        ans = cnt
print(ans)