BOJ 2468번 : 안전 영역 (Python/Silver 1)

2468번: 안전 영역

---

설명

🌟 문제 핵심 - 안전 영역이 최대인 것을 구하라.
나도 처음엔 무슨 소리인가 했는데, 영역이라는 것을 생각해야 한다. 강수량은 주어지지 않으므로 모든 강수량을 따져야 한다. 
 
다음과 같이 N = 5인 지역이 있다고 하자.

 

 

영역은 오른쪽, 왼쪽, 위, 아래가 이어져 있으면 한 영역으로 본다.

만약, 강수량이 0일 때 비가 오지 않음을 뜻하므로 잠기는 곳은 없다. 왼, 오, 위, 아래가 다 이어져있으면 하나의 영역으로 본다고 했으므로 안전 영역은 1이다. 
 

 

 

 

 

만약, 강수량이 4일 때 높이가 4이하인 지역은 잠긴다. 따라서 잠긴 곳을 칠하고 남은 영역을 보면, 총 5곳이다. 

(강수량이 3일 때는 안전 영역이 총 4개가 된다.)

 

 

 

 

 

만약, 강수량이 6일 때 높이가 6이하인 곳은 모두 잠긴다. 그래서 남은 영역은 총 4곳이다. 

강수량이 6이상이 되면 안전 영역은 점점 줄어들 것이다. 따라서 강수량이 4일 때가 안전 영역의 수가 최대이므로 안전 영역의 수는 5이다.

 

 

 

 

풀이

✓ 그래프 탐색 알고리즘 이용 - BFS 풀이

 

https://dev-cloud.tistory.com/161 -> 유사한 문제이다. BFS와 관련해서 더 자세한 설명이 있으니 봐보자.

Solution

#15:55 - 16:47 이후 풀이봄->보완점이 좀 필요했음. 보완하고 제출했는데 시간초과 걸림)
#문제 이해 완료(30분이나 걸렸다... 영역이라는 걸 생각 못했다.)

import sys
input = sys.stdin.readline
#bfs를 위해 deque 임포트
from collections import deque
N = int(input())
area = [list(map(int, input().split())) for _ in range(N)]
#최대 높이 찾기
max_value = max(map(max, area)) 
#오른쪽부터 시계방향으로 탐색
dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]

def bfs(rain, x, y): #rain = 강수량
    '''#이걸 추가하면 답은 나오나 시간초과 나옴
    # for문으로 area를 다 돌아서 강수량보다 낮은 곳을 check표시해
    for i in range(N):
        for j in range(N):
            if area[i][j] <= rain:
                area[i][j] = -1 #잠겼음을 나타냄
   '''
    q = deque()
    q.append((x, y))
    visited[x][y] = 1
    while q:
        x, y = q.popleft()

        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y

            if -1 < nx < N and -1 < ny < N:
                if area[nx][ny] > rain and visited[nx][ny] == 0:
                    visited[nx][ny] = 1  # 방문체크 후 큐에 넣음
                    q.append((nx, ny))


res = []
for rain in range(max_value):
    cnt = 0
    visited = [[0 for _ in range(N)] for _ in range(N)]  # 방문 표시
    for i in range(N):
        for j in range(N):
            #잠기는 곳은 반복문 돌면서 잠겼다는 표시 하지말고 해당되는 곳만 탐색하는 것이 훨씬 효율적이다.
            if visited[i][j] == 0 and area[i][j] > rain:
                bfs(rain, i, j)
                cnt += 1
    res.append(cnt)
print(max(res))