백준 2468 안전영역 파이썬

백준 2468 안전영역 풀이

접근방식

1. BFS 알고리즘을 활용하여 해결합니다.
2. 특정한 높이가 주어졌을 때, 해당 높이보다 높은 지역일 경우,
   visited 리스트를 True 값으로 바꿔줌으로써 방문처리해줍니다.
3. 우선 주의할 점은, 주어진 입력 중 가장 높은 높이와 동일한 비가 내릴 경우, 모든 지역이 잠기기 때문에 가장 높은 지역보다 -1 작은 값을 가지고 for문을 실행합니다.
4. 다음 주의할 점은, 잠기지 않은 지역이 발견되면 bfs 함수가 작동하면서 자연스럽게 주변에 잠기지 않은 지역을 탐색하게 됩니다.
5. 따라서, 안전영역의 갯수는 잠기지 않은 지역이 발견될 때마다 1씩 늘어난다고 볼 수 있습니다.
6. 이를 가지고 처음 높이가 결정되는 for문 마지막에 max 함수를 이용해서 안전영역의 최댓값을 갱신해줍니다.

import sys
from collections import deque

input = lambda: sys.stdin.readline().rstrip()

n = int(input())

arr = [list(map(int, input().split())) for _ in range(n)]

maxH = max(max(arr))

dr = [-1,0,1,0]
dc = [0,1,0,-1]

def bfs(a,b, visited, height):
    q = deque()
    q.append((a,b))
    while q:
        x, y = q.popleft()
        for i in range(4):
            nr = x + dr[i]
            nc = y + dc[i]
            if 0 <= nr < n and 0<= nc < n:
                if arr[nr][nc] > height and not visited[nr][nc]:
                    visited[nr][nc] = True
                    q.append((nr, nc))

result = 1
for h in range(maxH):
    cnt = 0
    visited = [[False]* n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if arr[i][j] > h and not visited[i][j]:
                cnt += 1
                bfs(i, j, visited, h)
    result = max(cnt, result)
print(result)

해당 문제는 실버1레벨의 DFS, BFS 문제였습니다.

dr, dc 리스트를 활용하거나 deque 자료구조를 활용하여 탐색을 하는 것은

다른 문제들과 동일했고, 유의해야 할 점은 두가지가 있습니다.

잠기지 않은 지역을 발견할 때마다 자연스럽게 안전영역이 늘어나도록 코드를 짜는 것과

따로 비의 높이가 주어지지 않기 때문에 주어진 지역의 높이 중 가장 높은 것 -1 까지 for문을 통해

갱신해주는 점입니다.

알고리즘도 모든 것과 마찬가지로 꾸준한 연습과 이해를 바탕으로 실력이 향상합니다.
Just do it & Keep steady