[ 그래프 이론-2468 ] 안전 영역(Python)

---

접근법

처음에는 N으로 입력값은 높이에 대한 안전 영역 을 계산하였지만 문제를 잘못 접근 한 것이었다.

높이가 최소인 1부터, 각 위치의 높이가 쵀대인 값 까지 모두 고려하였을 때, 안전 영역이 최대가 되는 경우를 생각해야 한다. 즉 높이가 1부터 최대로 H까지 존재한다면,1~H 이하인 지점을 모두 잠기게 만드는 상황을 고려해야 한다.

만약 H이하인 경우 모두 잠기기 때문에 1~H-1까지 고려해서 최대인 안전 영역 을 계산하면 된다.

 

dfs()로 접근하여 해결하였으며, 여러번 계산해야 하므로 할때마다 방문한 위치를 표시하기 위한 변수 visited와 안전 영역 의 개수인 cnt를 초기화 한다.

---

정답

 

import sys
sys.setrecursionlimit(10**9)

N = int(input())

land = []

di = [0,0,-1,1]
dj = [1,-1,0,0]

def dfs(i, j,h,visited):
    visited[i][j] = 1
    for k in range(4):
        I = i+di[k]
        J = j+dj[k]
        if 0 <= I < N and 0 <= J < N:
            if land[I][J] >h and visited[I][J] ==0:
                dfs(I,J,h,visited)

cnt = 0
max = 0

for i in range(N):
    tmp = list(map(int,sys.stdin.readline().split(" ")))
    land.append(tmp)
    for j in range(N):
        if land[i][j] > max:
            max = land[i][j] 

maxCnt = 0

for h in range(max):
    visited = [[0]*N for _ in range(N)]
    cnt = 0

    for i in range(N):
        for j in range(N):
            if land[i][j] > h and visited[i][j] == 0:
                cnt += 1
                dfs(i,j,h,visited)

    if cnt > maxCnt:
        maxCnt = cnt

print(maxCnt)

 

각 위치의 높이가 h보다 크고 아직 방문하지 않은 위치에 대하여 dfs를 적용하면 된다.

재귀적으로 동작하므로 sys.setrecursionlimit()를 해 줘야 한다.