반응형
https://www.acmicpc.net/problem/2468
2468번: 안전 영역
재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는
www.acmicpc.net
import sys
import copy
sys.setrecursionlimit(15000)
n = int(input())
max_num = -sys.maxsize
min_num = sys.maxsize
graph = []
for i in range(n):
lst = list(map(int,input().split()))
graph.append(lst)
max_num = max(max_num, max(lst))
min_num = min(min_num, min(lst))
## 이걸로 하면 문제 통과
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
## 이걸로 하면 메모리 초과 발생
#dx = [-1, 0, 1, 0]
#dy = [0, -1, 0, 1]
def dfs(x, y, h):
if map[x][y] <= h:
return
map[x][y]=0
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < n and map[nx][ny]>h:
dfs(nx, ny, h)
answer=1
for height in range(min_num, max_num+1):
regions = 0
map = copy.deepcopy(graph)
for j in range(n):
for k in range(n):
if map[j][k] > height:
dfs(j,k,height)
regions +=1
answer = max(answer, regions)
print(answer)DFS와 브루트포스를 이용하여 푸는 문제다.
다만, 메모리 초과 문제를 해결하려다 시간이 굉장히 오래 걸렸다.
원인은 정말 쌩뚱맞게도 dx, dy 부분이었다.
## 이걸로 하면 문제 통과
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
## 이걸로 하면 메모리 초과 발생
#dx = [-1, 0, 1, 0]
#dy = [0, -1, 0, 1]이상해서 질문에도 올려놓은 상태다.
- 배운 점
- import copy를 쓰고 deepcopy()를 쓰면 리스트의 리스트까지도 얕은 복사가 가능해짐
- 재귀횟수 제한을 import sys, sys.setrecursionlimit(15000)로 변경할 수 있다.
- dx = [-1,0,1,0]으로 안되던게 dx= [-1,1,0,0]으로 될 때가 있다...
댓글