[伯俊]7576号トマト、BFS、Deque

問題の説明

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

私の最初の答え

以前のようにlistをqueueとして使用するとタイムアウトします.listのpop(0)を使用すると、index=0の値がlistからポップアップされ、O(n)の時間的複雑さがあります.
O(1)時間の複雑さを持つdequeを用いてタイムアウト問題を解決する.Dequeについての整理はここです。本で行われている.

import sys
from collections import deque

N, M = map(int, sys.stdin.readline().split())

matrix = list()
queue =  deque()

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

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

days = [[0]*N for _ in range(M)]

def bfs():
    visited = [[0]*N for _ in range(M)]

    while queue:
        for _ in range(len(queue)):
            i, j = queue.popleft() 

            for direction in range(4):
                goX = i + dx[direction]
                goY = j + dy[direction]

                if goX>= 0 and goX < M and goY >= 0 and goY < N and visited[goX][goY] == 0 and matrix[goX][goY] == 0:
                    matrix[goX][goY] = 1
                    visited[goX][goY] = 1
                    days[goX][goY] = days[i][j] + 1
                    queue.append([goX, goY])

bfs()

ans = max(map(max, days))

bool = True
for i in range(M):
    if 0 in matrix[i]:
        bool = False

if bool:
    print(ans)
else:
    print(-1)

解けたら、ぜひ訪問状況をチェックしたいと思います.これはマトリクスの中でゼロの部分を探してbfsを行う論理であり,一度(通過できない部分を含まない)通過すれば1になるので,自動的にチェックにアクセスできる.
また,bfs()関数にはwhile文にキュー長に等しい繰返し文が加えられており,これも削除可能なコードである.この繰り返し文を加えた理由は,初熟トマトの個数が複数である場合に加えられる論理を考慮して全く必要としない論理である.

私の2番目の答え

次は上のコードの簡略化コードです.

import sys
from collections import deque

N, M = map(int, sys.stdin.readline().split())

matrix = list()
queue =  deque()

for i in range(M):
    input_map = list(map(int, sys.stdin.readline().split()))
    matrix.append(input_map)
    for j in range(N): # 입력받은 그래프에 이미 익은 (1) 토마토의 좌표를 queue에 저장
        if matrix[i][j] == 1:
            queue.append([i, j])

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

# 익은 날짜를 저장할 배열. 가장 큰 날짜를 구하는 게 이 문제의 정답이다.
days = [[0]*N for _ in range(M)]

def bfs():
    while queue:
        i, j = queue.popleft() # pop(0)과 같음. deque의 메소드

        for direction in range(4):
            goX = i + dx[direction]
            goY = j + dy[direction]

            if goX>= 0 and goX < M and goY >= 0 and goY < N and matrix[goX][goY] == 0:
                matrix[goX][goY] = 1
                days[goX][goY] = days[i][j] + 1
                queue.append([goX, goY])

bfs()
# 이차원 배열의 최대값
ans = max(map(max, days))

# 익지 않은(0) 토마토가 있을 시에는 -1을 리턴, 그렇지 않으면 최대 일수를 리턴
bool = True
for i in range(M):
    if 0 in matrix[i]:
        bool = False

if bool:
    print(ans)
else:
    print(-1)