백준 2468 안전영역

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

2468번: 안전 영역

📌 해결순서

처음에는

for i in range(1, max_height)

이렇게 비가 오는 높이를 1부터 시작했는데 런타임 에러가 났다

생각해보니까, 모든 지역의 높이가 1이면 비가 안와야지 안전영역의 갯수가 최대가 되기 때문에 비의 높이를 0부터 시작해야 했다.

1. 0부터 모든 지점중 최대 높이까지만 dfs 탐색을 진행한다. 최대 높이가 9인 경우, 비의 높이가 9라면 모든 지점이 잠기기 때문에 안전영역의 갯수가 0이 된다 따라서 8까지!

2. 어느 지점의 높이가 비의 높이보다 높고, 아직 방문하지 않은 지점이라면 dfs 탐색을 시작한다

3. 그 지점에서 4가지 방향에 대해서 조건을 만족한다면 깊이 우선 탐색으로 계속 방문 표시를 한다

4. 모든 지점에 대해서 탐색이 끝나면 높이를 1씩 추가해 가면서 반복한다

높이가 변경 될때마다 visited 배열을 초기화 해준다

 

📌 코드

import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline


def dfs(x, y, height):
    visited[x][y] = True

    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 not visited[nx][ny]:
                dfs(nx, ny, height)


n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

max_height = max(max(graph))
ans = -1
# 비가 안온 경우도 check. 그렇지 않으면 런타임 에러 발생

for i in range(max_height):
    visited = [[False] * n for _ in range(n)]
    cnt = 0
    for p in range(n):
        for q in range(n):
            if graph[p][q] > i and not visited[p][q]:
                cnt += 1
                dfs(p, q, i)
    ans = max(ans, cnt)

print(ans)