20. [2468] 안전 영역

1. 문제

장마철에 대비하여 민방위는 다음과 같이 계획하고 있습니다. 먼저 특정 지역의 표고 정보를 파악한다. 그런 다음 해당 지역에 폭우가 내릴 때 침수되지 않는 최대 안전 지역 수를 살펴보겠습니다. 이때 문제를 단순화하기 위해 장마철 강우량에 따라 일정 높이 이하의 모든 지점이 물에 잠긴다고 가정한다.

영역의 표고 정보는 N행과 열의 2차원 배열 형태로 주어지며, 배열의 각 요소는 해당 지점의 표고를 나타내는 자연수이다. 예를 들어 N=5인 면적의 높이 정보는 다음과 같다.

이제 위와 같은 지역에 많은 비가 내리므로 표고가 4 이하인 모든 지점이 물에 잠깁니다. 이 경우 침수된 지점은 다음과 같이 회색으로 표시됩니다.

물에 잠기지 않는 안전한 영역은 물이 없는 점이 위, 아래, 오른쪽 또는 왼쪽에 인접하고 크기가 가장 큰 영역입니다. 위의 경우 물에 잠기지 않은 안전한 영역이 5개 있습니다(꼭지점으로만 연결된 두 점은 인접하지 않은 것으로 취급).

또한 위 지역에서 높이 6 이하의 모든 지점이 침수될 정도로 많은 비가 내린다면 아래 그림과 같이 물에 잠기지 않는 안전지역이 4곳임을 확인할 수 있다.

따라서 물에 잠기지 않는 안전한 지역의 수는 장마철에 내리는 비의 양에 따라 달라진다. 위의 예와 같이 같은 지역에 내리는 강우량으로 모든 경우를 살펴보면 물에 잠기지 않는 안전한 지역이 가장 많은 곳이 5개라는 것을 알 수 있습니다.

지역의 고도에 대한 정보가 주어지면 우기 동안 물에 잠기지 않을 안전한 지역의 최대 수를 계산하는 프로그램을 작성하십시오.

• 입장 : 첫 번째 행에는 범위를 나타내는 2차원 배열의 행과 열의 수를 나타내는 숫자 N이 입력됩니다. N은 2 이상 100 이하의 정수이다. 두 번째 행부터 N행 각각에는 2차원 배열의 첫 번째 행부터 N행까지의 순서로 한 행씩 높이 정보가 입력된다. 각 줄에는 각 줄의 첫 번째 열부터 N번째 열까지 N 높이 정보를 나타내는 자연수가 공백을 사이에 두고 입력됩니다. 높이는 1에서 100 사이의 정수입니다.

• 누르다 : 첫 번째 줄에는 우기 동안 침수되지 않을 최대 안전 지역 수를 입력합니다.

두 번째 답변

1. bfs

from collections import deque

dx = (-1, 1, 0, 0)
dy = (0, 0, -1, 1)

def bfs(x, y, height):
    queue = deque(((x, y)))
    visited(x)(y) = 1

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

        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) > height and visited(nx)(ny) == 0:
                    queue.append((nx, ny))
                    visited(nx)(ny) = 1


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

max_height = 0
for i in range(n):
    for j in range(n):
        if graph(i)(j) > max_height:
            max_height = graph(i)(j)

ans = 0
for height in range(max_height):  # 비가 안오는 경우인 0부터 max-1까지 조회(max는 모든 지역이 물에 잠기므로 안전영역이 0임 고려할 필요가 없음)
    visited = ((0) * n for _ in range(n))  # 매 높이마다 조회를 해야하므로 visited를 매번 정의
    temp = 0
    for i in range(n):
        for j in range(n):
            if graph(i)(j) > height and visited(i)(j) == 0:  # 강수량보다 많이 온 곳 & 방문하지 않은 경우 bfs호출
                bfs(i, j, height)
                temp += 1

    if ans < temp:
        ans = temp

print(ans)

원천 : 친구

---

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

#2468: 안전한 지역

장마철에 대비하여 민방위는 다음과 같이 계획하고 있습니다. 먼저 특정 지역의 표고 정보를 파악한다. 그 후, 그 지역에 많은 비가 내리고 있을 때,

www.acmicpc.net