[白俊][Python]2468号安全区域

[白俊]2468号安全区域

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

問題の説明📖

防災庁は大雨の雨季に備えて、次のようなことを計画しています.まず、ある地域の高度な情報を理解します.そして、この地域が大雨の時に最大でどれだけの浸水しない安全区域を形成できるかを調べます.このとき,問題を単純化するために,雨季の雨量が一定の高さ以下のすべての場所が水没すると仮定した.
一部の領域の高さ情報は、行と列のサイズがそれぞれNの2次元配列の形で与えられ、配列内の各要素は、その点の高さを表す自然数である.例えば、以下はN=5の領域の高さ情報である.

現在、上のような地域では大雨が降っており、4より低いところはすべて水没しています.この場合、水没点は以下のようにグレーで表される.

水没しない安全区域とは、水没しない場所が上、下、右または左に隣接し、その大きさが最も大きい区域を指す.上記の場合、水没しない安全区域は5つある(死点付着のみとは思えない2つの地点が隣接している).
また、上記の地域で大雨が降って高さ6以下のすべての場所が水没した場合、水没しない安全区域は、下図のように4つ確認できます.

このように雨季によって降雨量が異なり、水没しない安全区域の個数も異なる.前例のように雨量によってすべての状況を調べた結果,水没しない安全区域の個数のうち最大は5であった.
地域の高さ情報を取得する場合は、雨季に浸水しない安全な地域の最大数を計算するプログラムを作成します.
入力
1行目は、ある領域の2次元配列を表す行数と列数Nを入力する.Nは2以上100以下の整数である.2行目からN行目まで、2次元配列の1行目からN行目までの高さ情報を順次入力します.各行において、各行の第1列から第N列までのN個の高さ情報を表す自然数がスペースを隔てて入力される.高さは1以上100以下の整数です.
しゅつりょく
第1行は雨季に浸水しない安全区域の最大数を出力する.
I/O例

質問へのアクセス💡

1.BFSの実施
2.0から最低価格まで水没しない島の数を計算する
3.カウントの中で最も高い値を求めて印刷します.

問題を解く💡

import sys
from collections import deque

N = int(input())
matrix = []
maxNum = 0


dx = [-1,1,0,0]
dy = [0,0,-1,1]
queue = deque()

for i in range(N):
    matrix.append(list(map(int, sys.stdin.readline().split())))
    for j in range(N):
        if matrix[i][j] > maxNum:
            maxNum = matrix[i][j]




def bfs(n):
    while queue:
        x,y = queue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or nx >= N or ny <0 or ny >= N:
                continue

            if matrix[nx][ny] > n and visited[nx][ny] == 0:
                queue.append((nx,ny))
                visited[nx][ny] = 1



answer = 0
for i in range(maxNum):
    visited = [[0]*N for _ in range(N)]
    cnt = 0
    for a in range(N):
        for b in range(N):
            if matrix[a][b] > i and visited[a][b]==0:
                queue.append((a,b))
                visited[a][b] = 1 # 방문처리
                bfs(i)
                cnt += 1
    answer = max(answer,cnt)

print(answer)

質問のヒント💡

本当に大間違いだ.エラーの原因は2つあります.
1.問題の理解不足
読み間違えて問題になったので、高さが5だと思ったら4以下のエリアにしかロックされません.
すなわち,5から水没しない島の個数を算出すると,5は水没しないことを示す.(n>=5)
5が閉まっていることを確認しなければなりません(n>5)
2.反例
常にメモリと時間秒を減らしたいので、島の数をチェックするrange範囲(1,maxnum)を選びました.問題の高さは1以上ですが、i=1ならどうせカウント値は1だと思います.島の高さを1より大きい2からチェックすれば時間が減ると思っていたのですが、ずっと間違っていました.
最終的にrangeの範囲を(maxnum)として正解した.反例をよく考えた.

1 1 1 1 
1 1 1 1 
1 1 1 1
1 1 1 1 

おかしいですね.簡単な反例を思い出しました.すべての高さが1の場合、2からチェックを開始し、カウント値はもちろん0です.2つ以上の高さがなければ、島がないことになります.
以前、多くのコーディングテストをしていたら、正解は当たり前だったのですが、ここで時間とメモリの戦いを聞きました.白俊を解いて本当に共感しました.メモリと時間を減らすために努力しているため、問題を理解するのはいつも間違っています.
効率も効率ですが、正解が基本なので、もっとよく理解して、正確に論理を立てる必要があります.