225. 안전 영역

백준

1. Python

BFS

import sys
input = sys.stdin.readline

n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]

cnt = 1
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs(x, y, h):
    q = []
    q.append((x,y))
    while q:
        x,y = q.pop()
        for i in range(0, 4):
            nx=dx[i]+x
            ny=dy[i]+y
            if nx>=0 and nx<n and ny>=0 and ny<n:
                if(visit[nx][ny]==0 and graph[nx][ny]>h):
                    visit[nx][ny]=1
                    q.append((nx,ny))


for number in range(max(map(max, graph))):
    land = 0
    visit = [[0] * n for _ in range(n)]
    for i in range(0, n):
        for j in range(0, n):
            if visit[i][j] == 0 and graph[i][j] > number:
                visit[i][j]=1
                bfs(i, j, number)
                land += 1
    if land > cnt:
        cnt = land

print(cnt)

메모리 초과

• recursionlimit 줄여주기

import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline

# 상 우 하 좌
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

def dfs(x, y, h):

    for m in range(4):
        nx = x + dx[m]
        ny = y + dy[m]

        if (0 <= nx < n) and (0 <= ny < n) and not visit[nx][ny] and graph[nx][ny] > h:
            visit[nx][ny] = True
            dfs(nx, ny, h)


n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]

ans = 1
for k in range(max(map(max, graph))):
    visit = [[False]*n for _ in range(n)]
    safe = 0
    for i in range(n):
        for j in range(n):
            if graph[i][j] > k and not visit[i][j]:
                safe += 1
                visit[i][j] = True
                dfs(i, j, k)
    ans = max(ans, safe)

print(ans)