백준 2468번 안전 영역 파이썬 DFS

https://www.acmicpc.net/problem/2468

2468번: 안전 영역

 

 

내 답안

import copy
import sys
sys.setrecursionlimit(10 ** 6)
 
def dfs(x, y):
    if x < 0 or y < 0 or y >= N or x >= N:
        return False
 
    if native_graph[x][y] == 1:
        native_graph[x][y] = 0
        dfs(x - 1, y)
        dfs(x, y - 1)
        dfs(x + 1, y)
        dfs(x, y + 1)
        return True
    return False
 
Max = 0
result = 0
N = int(input())
graph = []
for _ in range(N):
    graph.append(list(map(int, input().split())))
 
native_graph = copy.deepcopy(graph)
 
# 2차원 배열에서 가장 높은 숫자 찾기
height = 0
for _ in native_graph:
    for l in _:
        if l > height:
            height = l
 
for k in range(1, height + 1):
    for i in range(N):
        for j in range(N):
            if native_graph[i][j] >= k:
                native_graph[i][j] = 1
            else:
                native_graph[i][j] = 0
 
    result = 0
    for i in range(N):
        for j in range(N):
            if dfs(i, j):
                result += 1
 
    if Max < result:
        Max = result
 
    native_graph = copy.deepcopy(graph) # graph 초기화
 
print(Max)

---

Review

 

생각보다 아이디어 구상하는 건 어렵진 않았다.

하지만 물의 수위(k)마다 문제에서 같게 주어진 그래프로 생각을 해야 하기 때문에 깊은 복사를 해줘야 했다.

그래서 import copy 라이브러리에서 deepcopy() 함수를 썼다.

 

for k in range(1, height + 1):
    for i in range(N):
        for j in range(N):
            if native_graph[i][j] >= k:
                native_graph[i][j] = 1
            else:
                native_graph[i][j] = 0
 
    result = 0
    for i in range(N):
        for j in range(N):
            if dfs(i, j):
                result += 1
 
    if Max < result:
        Max = result
 
    native_graph = copy.deepcopy(graph) # graph 초기화

이 부분이

수위가 1 부터 가장 높은 수위의 까지 안전영역을 판별하는 코드이다.

max(max(native_graph)) 는 주어진 영역에서 가장 높은 수위이다.  (재 채점시 틀린답)

height 는 주어진 영역에서 가장 높은 수위이다.

다행히도 시간 초과는 없었지만

 

import sys
sys.setrecursionlimit(10 ** 6)

 

재귀스택을 늘려주지 않아서 런타임 에러 (RecursionError) 가 떳었다..ㅎ