[백준-2468] 안전영역

문제

재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다.

어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어지며 배열의 각 원소는 해당 지점의 높이를 표시하는 자연수이다. 예를 들어, 다음은 N=5인 지역의 높이 정보이다.

링크

풀이

처음에는 직관적으로 봤을 때 DFS를 통해서 풀면 될 듯하여 풀었다.
예제 입력으로 했을 때는 답이 다 잘 나왔는데 자꾸 제출만 하면 런타임 에러 (RecursionError) 가 떠가지고... 머리 쥐어 뜯었다

DFS

n = int(input())

graph = []
maxNum = []
visited = []
for i in range(n) :
    graph.append(list(map(int, input().split())))
    maxNum.append(max(graph[i]))

di = [-1, 1, 0, 0]
dj = [0,0,-1,1]

def dfs(i, j) :
    if i <= -1 or i >= n or j <= -1 or j >= n :
        return False
    if graph[i][j] > h and visited[i][j] == 0 :
        visited[i][j] = 1
        for d in range(4) :
            dfs(i + di[d], j + dj[d])
        return True
    return False

answer = []
# 비가 안 올 수도 있기 때문에 0 ~ 지역 중 최대로 높은 곳
num = max(maxNum)+1
for h in range(0, 10) :
    place = 0
    visited = [[0] * n for _ in range(n)]
    for a in range(n) :
        for b in range(n) :
            if graph[a][b] > h and visited[a][b] != 1 and dfs(a, b):
                place += 1
    answer.append(place)          

print(max(answer))

그래서 결국 BFS로 풀었다.

BFS

from collections import deque
n = int(input())

graph = []
maxNum = []
visited = []
for i in range(n) :
    graph.append(list(map(int, input().split())))
    maxNum.append(max(graph[i]))

da = [-1, 1, 0, 0]
db = [0,0,-1,1]

def bfs(a, b, h, visited) :
    queue = deque()
    queue.append((a, b))
    visited[a][b] = 1
    while queue :
        a, b = queue.popleft()
        for i in range(4) :
            na = a + da[i]
            nb = b + db[i]
            if na <= -1 or na >= n or nb <= -1 or nb >= n :
                continue
            if graph[na][nb] > h and visited[na][nb] != 1 :
                queue.append((na, nb))
                visited[na][nb] = 1

answer = []
for h in range(0, max(maxNum)+1) :
    visited = [[0] * n for _ in range(n)]
    result = 0
    for a in range(n) :
        for b in range(n) :
            if graph[a][b] > h and visited[a][b] == 0 :
            # 모든 노드 다 접근
                dfs(a, b, h, visited)
                result += 1 
    # 모든 노드 다 접근했다면 넣어주기
    answer.append(result)        

print(max(answer))            

1. 그래프랑 방문 여부 확인하는 배열 만들기
2. 비가 아예 안올 수도 있고, 비가 오더라도 지역의 최대 높이만큼 오면 어차피 다 잠기기 때문에 0부터 최대 높이까지 구하기
3. 모든 노드 다 접근하면서 bfs 로 구하기

다른 분들 DFS 풀이 보면서 해보기도 했고, 백준에서 뭐 오류날 때마다 늘려줘야한다 줄여줘야한다 어쩌구 그것도 다 해봤는데 안돼서 결국 BFS ..ㅠㅠ
알고리즘 상으로는 문제 없는 거 같은데 뭐가 문제인지 모르겠다.
앞으로 DFS 형태 문제라도 그냥 BFS 로 풀어야겠다.........................