😊 백준 2468 : 안전 영역

2468: 안전 영역

DFS/BFS 여섯 번째 문제!

📌 Try 1

def dfs(x, y):
    if x < 0 or x >= N or y < 0 or y >= N:
        return 0
        
    if visit[x][y] == 0 and graph[x][y] > i:
        visit[x][y] = 1
        
        dfs(x+1, y)
        dfs(x-1, y)
        dfs(x, y+1)
        dfs(x, y-1)
        return 1

    return 0

N = int(input())
graph, Hindex, result = list(), set(), list()

for _ in range(N):
    _input = list(map(int, input().split()))
    Hindex.update(_input)
    graph.append(_input)
    
for i in Hindex:
    visit, num = [[0 for _ in range(N)] for _ in range(N)], 0
    
    for x in range(N):
        for y in range(N):
            if visit[x][y] == 0 and graph[x][y] > i:
                num += dfs(x, y)
    result.append(num)
    
print(max(result))

시간 제한이 1초이기 때문에 입력된 지형 높이를 중복 없이 저장하고 저장된 높이만 탐색하려 했다. Hindex라는 set를 만들고 저장했다.
이 부분이 문제였다. 안 잠기는 경우가 있다는 걸 고려하지 않은 거다.

위 코드는 런타임 에러 (RecursionError)가 떴다.
python에서 재귀 depth는 3000인데 이걸 고려하지 못했다.
N <= 100 이므로 depth는 10000을 훨씬 넘는다.

📌 Try 2

def dfs(x, y):
    if x < 0 or x >= N or y < 0 or y >= N:
        return 0
        
    if visit[x][y] == 0 and graph[x][y] > i:
        visit[x][y] = 1
        
        dfs(x+1, y)
        dfs(x-1, y)
        dfs(x, y+1)
        dfs(x, y-1)
        return 1

    return 0

N = int(input())
graph, result = list(), list()

for _ in range(N):
    _input = list(map(int, input().split()))
    graph.append(_input)
    
for i in range(2, 101):
    visit, num = [[0 for _ in range(N)] for _ in range(N)], 0
    
    for x in range(N):
        for y in range(N):
            if visit[x][y] == 0 and graph[x][y] > i:
                num += dfs(x, y)
    result.append(num)
    
print(max(result))

위 코드는 단순히 Hindex만 삭제한 코드이다.
이 코드도 문제가 있는데, for의 범위가 (2,101)이다. 0부터 탐색해야 하는데,,,

📌 Try 3

import sys
sys.setrecursionlimit(100000)

def dfs(x, y):
    if x < 0 or x >= N or y < 0 or y >= N:
        return 0
        
    if visit[x][y] == 0 and graph[x][y] > i:
        visit[x][y] = 1
        
        dfs(x+1, y)
        dfs(x-1, y)
        dfs(x, y+1)
        dfs(x, y-1)
        
        return 1

    return 0

N = int(input())
graph, result = list(), list()

for _ in range(N):
    _input = list(map(int, input().split()))
    graph.append(_input)
    
for i in range(0, 101):
    visit, num = [[0 for _ in range(N)] for _ in range(N)], 0
    
    for x in range(N):
        for y in range(N):
            if visit[x][y] == 0 and graph[x][y] > i:
                num += dfs(x, y)
    result.append(num)
print(max(result))

맨 위의 sys.setrecursionlimit(100000)는 재귀 depth를 임의로 늘려준 것이다.

for의 범위 역시 (0, 101)로 수정했다.

결과는,,, 맞았습니다!!

.
.
.

앞으로 범위를 고려해서 dfs를 써야겠습니다.😂

범위가 크면, dfs를 for로 구현하거나, bfs를 사용해야겠습니다.

🎁 Reference