[白俊]https://www.acmicpc.net/problem/7576トマト(2次元)
[白俊]https://www.acmicpc.net/problem/7569トマト(三次元)
2 Dトマトと3 Dトマトの問題を解いてみます.
2次元トマトと3次元トマトはほぼ似たような問題ですが、よく知らないbfsアルゴリズムと3次元配列を一緒に処理するので、頭の中でうまく描けないので、もっと複雑な感じがします.
比較的容易な二次元トマト問題をもとに,解法を整理した.

2 Dトマト

input

for i in range(N):
    tmp = list(sys.stdin.readline().split())
    for j in range(M):
        if '-1' == tmp[j]:
            visited[i][j] = -1
        elif '1' == tmp[j]:
            que.append([i, j])
            visited[i][j] = 1
    box.append(tmp)

Input段階でやるべきこと 処理トマトがある場所を訪問します。 queにトマトが入っている位置。 トマトがない位置-1を処分します。 =>後でトマトがあったのにアクセスできなかったので0しか残っていなかったのですが、

BFS

def bfs():
    global m					# 최댓값을 저장
    while len(que) != 0:
        y, x = que.popleft()	# 넣어두었던 좌표 y, x

        for i in range(4):		# 4방향 탐색할 좌표 설정
            nx = x + dx[i]		
            ny = y + dy[i]

            if 0 <= ny < N and 0 <= nx < M:	# 탐색할 좌표가 범위 안에 있나??
                if visited[ny][nx] == 0 and box[ny][nx] == '0':	# 방문한 적이 없고 익지 않은 토마토가 있는가?
                    box[ny][nx] = 1	# 토마토를 익힘
                    visited[ny][nx] = visited[y][x] + 1	# 익히는 데 걸린 날짜 저장
                    m = m if m > visited[ny][nx] else visited[ny][nx]
                    que.append([ny, nx])	#익힌 토마토 좌표를 큐에 저장

    for n in range(N):	# 하나라도 0이 남았다면 -1 리턴
        if 0 in visited[n]:
            return -1
    else:
        return m-1

deque Pythonでキューを使用する場合,listのpop(0)を使用すると,原理的にリストの最後のインデックスから順次アクセスするため,時間的複雑度はO(N)である.本題では,O(1)に減らすために集合ライブラリを導入し,queリストをdequeとする.

熟知した日付は、アクセスリストの対応する座標に格納されます。 どの座標の中で最後のトマトが熟すか分からないので、最低価格を格納するために変数mを別途作りました。 スタート地点のトマトは既にアクセスリストに1が保存されています。 (熟れていますが、処理には1日かかるようです) (処理しないと、熟していないトマトを区別するのが難しい) 最後にm-1対価をします。

BFS問題ではアクセスとどこでアクセス処理を行うかが重要! この問題については,queに登録する前に必ず処理しなければならない. 複数のトマトがある場合は、queを入れる順番でトマトの方向ごとに交互に行い、アクセス処理を行う前にqueを入れると、複数の方向から近い座標が同時に1つのトマトに近づくので頭が痛くなります。これで白俊はタイムアウトに処理されます。

完全なコード

# [백준] https://www.acmicpc.net/problem/7576 토마토(2차원)
# BFS '최소 날짜'
import sys
import collections

sys.stdin = open('basic/BOJ7576.txt')

M, N = list(map(int, sys.stdin.readline().split()))
box = []
que = collections.deque([])
visited = [[0] * M for _ in range(N)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
day = 0
m =0	# 최댓값을 저장하는 변수
idx = []

for i in range(N):
    tmp = list(sys.stdin.readline().split())
    for j in range(M):
        if '-1' == tmp[j]:
            visited[i][j] = -1
        elif '1' == tmp[j]:
            que.append([i, j])	# 토마토의 위치를 미리 que에 넣고 시작
            visited[i][j] = 1
    box.append(tmp)


def bfs():
    global m
    while len(que) != 0:
        y, x = que.popleft()

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

            if 0 <= ny < N and 0 <= nx < M:
                if visited[ny][nx] == 0 and box[ny][nx] == '0':
                    box[ny][nx] = 1
                    visited[ny][nx] = visited[y][x] + 1
                    m = m if m > visited[ny][nx] else visited[ny][nx]
                    que.append([ny, nx])

    for n in range(N):
        if 0 in visited[n]:
            return -1
    else:
        return m-1


for n in range(N):
    if '0' in box[n]:
        print(bfs())
        exit(0)
else:
    print(0)

3 Dトマト

3次元トマト問題は2次元で高さだけを増やす方向とfor文でif文を増やすと似た方向に戻ります.

for k in range(H):
    temp =[]
    for i in range(N):
        tmp = list(sys.stdin.readline().split())
        for j in range(M):
            if '-1' == tmp[j]:
                visited[k][i][j] = -1
            elif '1' == tmp[j]:
                que.append([k, i, j])
                visited[k][i][j] = 1
        temp.append(tmp)
    box.append(temp)

input

3 Dリストを受信する過程で、1 Dリストをtmpリストに保存し、tmpを2 D tempリストに再保存するトラブルに遭遇しました。 tempリストをボックスに再保存することで解決しました。 △これよりもっといい方法があるようだが、まだ方法が見つからない。

# [백준] https://www.acmicpc.net/problem/7569 토마토(3차원)
# BFS '최소 날짜'

import sys
import collections

sys.stdin = open('test/04.txt')

M, N, H = list(map(int, sys.stdin.readline().split()))
box = []
que = collections.deque([])
visited = [[[0] * M for _ in range(N)] for _ in range(H)]
dx = [0, 0, -1, 1, 0, 0]
dy = [0, 0, 0, 0, -1, 1]
dh = [-1, 1, 0, 0, 0, 0]
m = 0

for k in range(H):
    temp =[]
    for i in range(N):
        tmp = list(sys.stdin.readline().split())
        for j in range(M):
            if '-1' == tmp[j]:
                visited[k][i][j] = -1
            elif '1' == tmp[j]:
                que.append([k, i, j])
                visited[k][i][j] = 1
        temp.append(tmp)
    box.append(temp)


def bfs():
    global m
    while len(que) != 0:
        h, y, x = que.popleft()

        for i in range(6):
            nh = h + dh[i]
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= ny < N and 0 <= nx < M and 0 <= nh < H:
                if visited[nh][ny][nx] == 0 and box[nh][ny][nx] == '0':
                    box[nh][ny][nx] = 1
                    visited[nh][ny][nx] = visited[h][y][x] + 1
                    m = m if m > visited[nh][ny][nx] else visited[nh][ny][nx]
                    que.append([nh, ny, nx])


    for h in range(H):
        for n in range(N):
            if 0 in visited[h][n]:
                return -1
    else:
        return m-1


for h in range(H):
    for n in range(N):
        if '0' in box[h][n]:
            print(bfs())
            exit(0)
else:
    print(0)