[그래프] Python - 2468번, 안전 영역

www.acmicpc.net/problem/2468

import sys
sys.setrecursionlimit(20000)

input = sys.stdin.readline

N = int(input())
Map = []
for _ in range(N):
    Map.append(list(map(int, input().split())))

stateMap = None


def getSafeZone(h):
    global stateMap
    stateMap = [[0]*N for _ in range(N)]
    cntSafeZone = 0
    for i in range(N):
        for j in range(N):
            if Map[i][j] > h and stateMap[i][j] == 0:
                cntSafeZone += 1
                dfs(i, j, h)
    return cntSafeZone


def dfs(x, y, h):
    global stateMap
    stateMap[x][y] = 1

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

    for i in range(4):
        curX, curY = x+dx[i], y+dy[i]
        if(0 <= curX <= N-1 and 0 <= curY <= N-1):
            if stateMap[curX][curY] == 0:
                if Map[curX][curY] > h:
                    dfs(curX, curY, h)


maxSafeZone = 0
for i in range(0, 101):
    cur = getSafeZone(i)
    if cur == 0:
        break
    maxSafeZone = max(maxSafeZone, cur)
print(maxSafeZone)

getSafeZone()는 비가 h만큼 올 때 안전한 영역을 구하는 함수입니다. 우선 stateMap[][]에는 각 위치가 잠겼는지(0) 안전한지(1)를 저장하는 변수이며 디폴트값은 0입니다. 전체 영역을 쭉 돌면서, h보다 높으면서 stateMap이 0(디폴트, 아직 고려하지 않은 위치를 의미함)일 때, 함수에서 반환할 cntSafeZone을 1 증가시키고 dfs를 돌립니다.

dfs는 인접한 안전한 지역을 모두 돌면서 stateMap을 갱신시켜줍니다. 따라서, 하나의 안전 영역 전체를 1로 바꿔주기 때문에, getSafeZone에서 dfs로 다신 접근할 일이 없습니다.

마지막으로, 0 until 100으로 getSafeZone()을 돌려서 최댓값을 저장하고 출력을 합니다. 다만, getSafeZone()으로 얻은 값이 0일 경우(모두 잠길 경우), i를 아무리 더 올려도 모두 0이므로 그곳에서 break를 합니다.