[파이썬]백준 2468 안전영역

링크

백준 2468 안전영역

dfs를 사용해 풀었다.
가장 높은 지점인 top을 찾아주고
rain을 1씩 증가시키면서 rain이 top과 같을 때 까지 반복해서 탐색했다.

정답 코드

import sys
sys.setrecursionlimit(100000)

def dfs(r, c, rain):
    for i in range(4):
        nr = r + dr[i]
        nc = c + dc[i]
        if 0 <= nr < N and 0 <= nc < N:
            if visit[nr][nc] == 0 and land[nr][nc] > rain:
                visit[nr][nc] = 1
                dfs(nr, nc, rain)


N = int(input())
land = [list(map(int, input().split())) for _ in range(N)]
top = max(map(max, land))
visit = [([0] * N) for _ in range(N)]
maxi = 0 #영역의 최댓값
tmp = 0 #영역의 수
rain = 0

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

for _ in range(top + 1):
    for i in range(N):
        for j in range(N):
            if visit[i][j] == 0 and land[i][j] > rain:
                visit[i][j] = 1
                tmp += 1 #한 영역을 찾으면 영역 +1
                dfs(i, j, rain)
    if tmp >= maxi:
        maxi = tmp #최댓값 갱신
    visit = [([0] * N) for _ in range(N)] #방문초기화
    tmp = 0 #영역의 갯수 초기화
    rain += 1

print(maxi)

알게된 것👨‍💻

• 무난무난