Python-2468-안전영역

안전 영역 click

각 지역의 높이가 주어지고, 높이별로 물에 잠기지 않는 안전영역의 최대 개수를 구하는 문제이다.

먼저 지역의 최대 높이와 최소 높이를 구해서 탐색할 높이의 범위를 정한다.

범위 내에서 각 높이에 대해 안전영역의 개수를 구해야 한다. 이때, 인접한 영역들은 하나의 영역으로 세아리는 방법에 대해서 알아보자.

---

• (0,0)부터 물에 잠기지 않은 영역을 탐색해 나가자.

• 물에 잠기지 않은 영역을 발견하면, 해당 영역을 시작으로 물에 잠기지 않은 인접한 영역들을 모두 찾아줘야 한다. 이때, 인접한 영역을 다시 방문해서 중복으로 숫자를 세는 일이 없도록, visit 리스트를 활용했다. 기본 값은 True이고, 방문한 점들에 대해서 False로 변경시켜 주었다.

• 물에 잠기지 않은 인접 영역들을 탐색할 때, BFS를 사용했지만 다른 방법으로 탐색해나가도 상관은 없다. 이 포스팅에서는 BFS에 대해서 별도로 다루지 않을 예정이다.

• 영역들을 탐색해 나갈 때, 인접 영역들의 방문 여부를 확인하고, 방문하지 않았던 점들만 탐색한다.

• 문제의 예제를 약간 변형했다.

• 최대, 최소 높이는 각각 2와 9이다. 따라서, 2부터 9까지의 높이에 대해 각각 탐색해야 한다. 그림에서는 4이하의 구역이 침수되는 경우와 5이하의 구역이 침수되는 경우만 다루었다.

4 이하의 구역이 침수된 경우

• (0,0)부터 (5,5)까지 안전영역을 탐색해 나가자.
• (0,0)은 안전영역이고, BFS탐색을 통해 (0,1)도 인접한 안전영역임을 알았다. visit리스트에서 두 점의 정보를 False로 변경해, 방문 표시를 해준다.
• (0,0)을 탐색했으니, 오른쪽으로 한 칸 이동한다. (0,1)도 안전영역이지만, 이미 방문했던 점임으로 지나친다.
• 다음 안전영역은 (0,3)에 위치해있다. 이 영역은 처음 방문했던 점임으로, BFS탐색을 시작한다. BFS를 통해 (0,4)와 (1,4)도 인접한 안전영역임을 확인할 수 있다.
• 이 과정들을 모든 점에 대해서 반복해주면, 4이하의 구역들이 침수된 경우에 4개의 안전영역이 존재함을 알 수 있다.

5 이하의 구역이 침수된 경우에 대해서도 마찬가지이다.

2부터 9까지 탐색하며 안전영역의 최대 개수를 구하자.

---

CODE

import sys
read=sys.stdin.readline
from collections import deque

dx=[1,0,0,-1]
dy=[0,1,-1,0]

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

#지역 최대, 최소 높이 저장
max_h=0
min_h=sys.maxsize
for h in height:
    for x in h:
        max_h=max(max_h,x)
        min_h=min(min_h,x)

#h높이만큼 물이 찼을 때, 안전영역 갯수 탐색
def safe(h):
    global count
    #해당 지역을 방문했는지 확인
    visit = list(list(True for _ in range(n)) for _ in range(n))
    for i in range(n):
        for j in range(n):
            #물에 잠기지 않았고, 최초로 방문하는 점들에 대해 탐색
            if visit[i][j] and height[i][j]>=h:
                #영역이 한 곳 추가 되었음으로 'count += 1'
                count+=1
                #BFS 탐색을 통해 물에 잠기지 않은 인접영역 방문처리
                point = deque([[i,j]])
                visit[i][j]=False
                while point:
                    a,b=point.popleft()
                    for x,y in zip(dx,dy):
                        ax,by=a+x,b+y
                        if 0<=ax<n and 0<=by<n and visit[ax][by] and height[ax][by]>=h:
                            visit[ax][by]=False
                            point.append([ax,by])

answer=1
for h in range(min_h,max_h+1):
    count=0 #h높이 미만의 지역들이 침수되었을 때 안전영역의 개수
    safe(h)
    answer=max(answer,count)

print(answer)

틀린 부분이 있을 수 있습니다. 피드백 주시면 고치도록 하겠습니다! 감사합니다.👍

[꼭 다시 풀어보기]