[BOJ]Pythonのセキュリティエリア

2468安全区域を解き放せ!
こんにちは!DevJunku
今日は2468安全区域の問題を解きます.これは最も代表的なBFS問題である.[上下三角移動](Up Down Triangulation)キューを使用すると、すぐに問題を解決できます.
問題は難しくない.最近アルゴリズムを少なく解いて、髪をコードします.書きました.ほほほ、いくつかの解答の方法の問題を暗記して近づきやすい長所があって、だからたまにつまらない時解答することができます.では、始めましょう.
問題の説明から雨季であることがわかりますが、雨季はどれだけ雨が降ったか教えてくれませんでした.入力値として、雨季に発生する可能性のある雨水量は높이는 1이상 100 이하의 정수이다.である.100回繰り返して一番目立つ部分を見つければいいのですしたがって、2 D配列内のすべての要素を毎回チェックするには、100回の演算が必要です.さらに最も重要なのは、四半期ごとに問題の配置を入力し、それを使用してアクセス配列を作成し、そのアクセス配列を使用してBFSを回転させることです.水没せずに移動可能な領域であれば、アクセスしたことのない要素を上下左右にチェックし、その領域の個数を計算するだけで同じ領域を移動できます.もちろん、1つのエリアの個数はBFSを実施した回数でしょう!
最後に、出力値が最も多い領域数です.四半期ごとに1つの領域数を保存し、最終的な正解数に更新すると、問題が解決します.私が作成したコードは次のとおりです.

from collections import deque 

# deque를 사용하는 이유는 시간 복잡도를 줄이기 위해서입니다.
# pop(n)은 시간복잡도가 O(n)이지만 deque의 popleft()는 시간 복잡도가 O(1)입니다.

n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]

d = [(1, 0), (0, 1), (-1, 0), (0, -1)]

def bfs(x, y): # BFS 체크
    queue = deque([(x, y)])
    while queue:
        cx, cy = queue.popleft()
        for dx, dy in d:
            nx, ny = cx + dx, cy + dy 
            if 0 <= nx < n and 0 <= ny <n:
            # 새로 계산한 인덱스가 배열 범위에 있는지 체크
                if not visited[nx][ny]:
                # 방문하지 않았다면, 방문!
                    visited[nx][ny] = True
                    queue.append((nx, ny)) 그러면서 queue에 저장


final_cnt = 0 # 최종 답
for i in range(1, 101): # 문제 요구로 인해 100번 순회
    repeat_cnt = 0 # 하나의 반복으로 인해 매번 영역 개수를 표기하기 위한 변수 매번 0으로 초기화
    visited = [[False for _ in range(n)] for _ in range(n)] # 방문 배열
    for j in range(n):
        for k in range(n):
            if arr[j][k] < i:
                visited[j][k] = True # 비로 인해 잠긴 부분은 방문하지 않아야 해서 방문 배열에서 방문했다고 표시

    for i in range(n):
        for j in range(n):
            if not visited[i][j]: # 다시 돌면서 bfs를 사용
                repeat_cnt += 1 # 이 때 마다 영역의 개수를 세어줌
                bfs(i, j)

    if repeat_cnt > final_cnt: # 영역의 최대값을 구하기 위한 부분
        final_cnt = repeat_cnt

print(final_cnt) # 마지막으로 출력!

終わりだ!