🔍 Problem

2468 안전 영역

⚡️ 사용한 알고리즘

sample

📃 Input&Output

📒 해결 과정

1️⃣ 높이 중에서 가장 높은 높이를 구하고 그 높이까지 비의 범위를 가정한다. (비의 범위 : 0~max_height)  
2️⃣ BFS를 사용하여 상하좌우 탐색 기준에서 현재 높이보다 큰 좌표만 방문한다.  
3️⃣ 2번을 비의 범위만큼 반복한다.  
4️⃣ 영역의 개수 중에서 가장 큰 값을 반환한다.

❗주의점

1. 비의 범위를 0부터 max_heigh까지 생각해야할 것. (문제가 친절하지 않다. 현실이 그렇듯이)
2. cnt(영역 카운트)의 선언 위치와 vst 리스트의 선언 위치를 잘 생각해서 구현할 것. (필자는 비의 높이를 기준으로 반복하는 for문 바로 아래에 선언하므로써 두개가 매번 초기화되게 함.)

💻 Code

import sys
from collections import deque

N = int(sys.stdin.readline())


mat = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

max_num=0

for i in mat:
    for j in i:
        if max_num<j:
            max_num=j
            

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

result=[]

def bfs(x, y,vst, h):
    que = deque([])
    que.append((x, y))
    vst[x][y] = True

    while que:
        x, y = que.popleft()
        for i in range(4):
            next_x, next_y = x + dx[i], y + dy[i]
            if next_x >= 0 and next_y >= 0 and next_x < N and next_y < N:
                if mat[next_x][next_y] > h and vst[next_x][next_y] == False:
                    que.append((next_x, next_y))
                    vst[next_x][next_y] = True

    
result=0

for k in range(0,max_num+1):
    vst = [[False] * N for _ in range(N)]
    cnt = 0
    
    for i in range(N):
        for j in range(N):
            if vst[i][j] == False and mat[i][j] > k:
                bfs(i, j, vst, k)
                cnt+=1
                
    if result<cnt:
        result=cnt

print(result)

🤔 느낀점

쉬운 문제였는데도 비가 오지 않는 경우도 고려해야하고 3중 for문이 들어가다 보니 고려할게 많아져서 신경쓸게 많았다. 하지만 단계별로 디버그를 하면서 이를 해결하였다.