파이썬 | 백준 | 2468 | 안전 영역

solution

1. dfs 이용

2. 빗물의 높이는 1이상 100이하 & 안 잠길 수도 있음 → for i in range(101)

3.sys.setrecursionlimit(50000)

# 2468, 안전 영역
import sys
sys.setrecursionlimit(50000)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

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

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < N and 0 <= ny < N:
            if area[nx][ny] > h and visited[nx][ny] == 0:
                dfs(h, nx, ny)

def dfsAll(h):
    cnt = 0     # 안전 영역의 갯수
    for i in range(N):
        for j in range(N):
            if area[i][j] > h and visited[i][j] == 0:
                cnt += 1
                dfs(h, i, j)
    return cnt

N = int(sys.stdin.readline())

area = []
for _ in range(N):
    area.append(list(map(int, sys.stdin.readline().split())))

max_cnt = 0
for i in range(101):
    visited = [[0]*N for _ in range(N)]
    max_cnt = max(max_cnt, dfsAll(i))

print(max_cnt)

36888KB
1636ms

 

문제 출처 https://www.acmicpc.net/problem/2468

2468번: 안전 영역