[白俊-2468]安全区域

質問する
防災庁は大雨の雨季に備えて、次のようなことを計画しています.まず、ある地域の高度な情報を理解します.そして、この地域が大雨の時に最大でどれだけの浸水しない安全区域を形成できるかを調べます.このとき,問題を単純化するために,雨季の雨量が一定の高さ以下のすべての場所が水没すると仮定した.
一部の領域の高さ情報は、行と列のサイズがそれぞれNの2次元配列の形で与えられ、配列内の各要素は、その点の高さを表す自然数である.例えば、以下はN=5の領域の高さ情報である.
リンク
に答える
最初は,直感的にDFSで解決すればよい.
サンプルで入力したときは答えはよかったのですが、いつもコミットしているとランタイムエラーが発生します...頭をつかんだ
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))            

パターンを作成し、アクセス状況を確認する配列

は雨が全然降らないかもしれません.雨が降っても、地域の最大の高さまで行けば、どうせ水没するので、0から最大の高さまで

を求めます.

はすべてのノードにアクセスし、bfsを使用して

を取得する.
他の人はDFS解答を見ながらやったことがありますが、Baek Junでエラーが発生したときに増やすべきで、減らすべきで、それもやったことがありますが、成功しませんでした.結局BFS...ううう
アルゴリズム的には問題ないようですが、何か問題があるのか分かりません.
これからDFS形態の問題でもBFSで解決していく・・・・・・・・・・・