2468번. 안전 영역

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

 

 

 

안전 영역이 나누어진 영역의 최댓값이라니 이런 무능한 재난청이 다 있나 싶었지만 어쨌든 문제를 풀었다.

문제를 풀 때 주의하거나 유의하면 좋을 점들은 다음과 같다.

 

1. 강수량 범위를 정해서 시작할 것

2. 전체 지역을 처음부터 검사하고 visited 배열을 만들어서 방문 체크를 하되 강수량 별로 초기화 할 것

3. dfs를 시작하는 지점도 visited 체크하는 것을 잊지 말 것

4. 각각의 안전한 지역 수를 셀 필요는 없음

 

import sys


# 비의 양(rain)에 따라 안전지대 수를 계산
def dfs(rain, row, col, check):
    stack = [[row, col]]

    while stack:
        r, c = stack.pop()
        for nR, nC in [[r+1, c], [r-1, c], [r, c+1], [r, c-1]]:
            if 0 <= nR < n and 0 <= nC < n:
                if not check[nR][nC]:
                    if board[nR][nC] > rain:
                        stack.append([nR, nC])
                check[nR][nC] = 1


if __name__ == '__main__':
    n = int(sys.stdin.readline())
    board = []
    maxRain = 0  # max height
    # 최대 높이를 구하고 그것을 강수량 범위로 정한다
    for _ in range(n):
        tmp = list(map(int, sys.stdin.readline().split()))
        maxRain = max(maxRain, max(tmp))
        board.append(tmp)

    maxSafe = 0
    for rain in range(maxRain):
        safeZone = 0
        visited = [[0 for _ in range(n)] for _ in range(n)]  # 강수량 별로 초기화
        for i in range(n):
            for j in range(n):
                if not visited[i][j] and board[i][j] > rain:  # 침수 아닌 지역부터 시작
                    visited[i][j] = 1  # dfs를 시작하는 지점도 방문 체크를 잊지 말 것
                    dfs(rain, i, j, visited)
                    safeZone += 1
        maxSafe = max(maxSafe, safeZone)

    print(maxSafe)