BAEKJOON #7576(BFS, DFS)
名トマト
ソース:白駿#7576
タイムアウトメモリ制限毎秒256 MB
質問する
チョルスのトマト農場にはトマトを保管する大きな倉庫がある.トマトは下図のように1つずつ四角い格子に入れて倉庫に保管しています.
倉庫に保管されているトマトの中には、熟しているものもあれば、まだ熟していないものもあります.1日保管した後、熟したトマトに隣接する未熟のトマトは、熟したトマトの影響を受けて成熟する.1つのトマトの隣接する場所は、左、右、前、後の4つの方向に位置するトマトを意味する.対角線方向に影響を与えないトマトは、トマトが自分で成熟しないと仮定します.哲洙は倉庫に保管されているトマトが何日で熟れるか、最低日数を知りたいと思っている.
倉庫にトマトのチェックボックスの大きさ、熟したトマトと未熟なトマトの情報を保管している場合、数日後には、トマトが熟しているかどうか、最低日数を求めるプログラムを作成します.しかし、箱のいくつかの格にはトマトが入っていないかもしれません.
入力
最初の行は、ボックスのサイズを表す2つの整数M,Nを与える.Mは箱の横格子数,Nは箱の縦格子数を表す.しかし,2≦M,N≦1000であった.2行目から、1つの箱に保存されているトマトの情報が提供されます.つまり、2行目からN行目まで、箱の中のトマトの情報が出てきます.1本の線上で、箱の横線のトマトの状態はM個の整数である.整数1は熟したトマトを表し、整数0は未熟のトマトを表し、整数-1はトマトを含まない格子を表す.
トマトが1つ以上ある場合にのみ入力します.
しゅつりょく
トマトがすべて熟成した最小日付を印刷します.保存からすべてのトマトが熟成している場合は0を、トマトが熟成していない場合は-1を出力します.
I/O例
入力例1
6 4
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1
サンプル出力1
8
入力例2
6 4
0 -1 0 0 0 0
-1 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1
サンプル出力2
-1
入力例3
6 4
1 -1 0 0 0 0
0 -1 0 0 0 0
0 0 0 0 -1 0
0 0 0 0 -1 1
サンプル出力3
6
入力例4
5 5
-1 1 0 0 0
0 -1 -1 -1 0
0 -1 -1 -1 0
0 -1 -1 -1 0
0 0 0 0 0
サンプル出力4
14
入力例5
2 2
1 -1
-1 1
サンプル出力5
0
に答える
説明する
BFS:pythonデータ構造Deque.
まず、各レベル(=depth)を区別する必要があります.したがって、tempにlevel 0に相当する座標を加え、temp自体をキューに入れる.
levelを1つ増加するたびに、日付を計算するために1日増加します.
このようにtempでlevelを区別し、tempが0の瞬間、キューに入れられるものがなくなったため、unripe(茹でていないトマト)が0の場合は日数を返し、そうでなければ-1(届かない場合)を返します.
python code(DFS)
# 백준 7576번 BFS
from sys import stdin
from collections import deque
def solution(n, m, box):
dx = [0, -1, 0, +1]
dy = [+1, 0, -1, 0]
# rotten = 0 # 썩은 토마토 개수 (필요없었음)
# count = 0 # 익게 한 토마토 개수(필요없었음)
unripe = 0 # 덜 익은 토마토 개수
days = 0 # 흐른 일 수
queue = deque()
temp = []
for i in range(n):
for j in range(m):
if box[i][j] == 1:
temp.append((i, j)) # 시작점 모으기
elif box[i][j] == 0:
unripe += 1
# else:
# rotten += 1 # 썩은거 골라내기 ... 굳이 있을 필요가 있을까?
queue.append(temp)
while queue:
temp_list = queue.popleft() # 리스트 단위로 level 구분 짓기
arr = [] # 다음 level에 들어갈 위치들
for col, row in temp_list:
for l in range(4):
if 0 <= col+dx[l] < n and 0 <= row+dy[l] < m:
if box[col+dx[l]][row+dy[l]] == 0:
box[col+dx[l]][row+dy[l]] = 1
arr.append((col+dx[l], row+dy[l]))
unripe -= 1
if len(arr) == 0: # 다음 level에서 추가 된 것이 없고
if unripe == 0: # 덜 익은 토마토도 없을 때 (완료된 상태)
return days
else: # 더 이상 익게할 수 있는 토마토가 없을 때 (미완료된 상태 : -1)
return -1
else:
days += 1
queue.append(arr)
# return days : 이것도 굳이 필요없음 어차피 len(arr)== 0 에서 다 걸러짐
n, m = map(int, stdin.readline().split())
box = []
for i in range(m):
box.append(list(map(int, stdin.readline().split())))
print(solution(m, n, box))
Reference
この問題について(BAEKJOON #7576(BFS, DFS)), 我々は、より多くの情報をここで見つけました https://velog.io/@nathan29849/BAEKJOON-7576BFS-DFSテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol