196. 토마토
1) 어떤 전략(알고리즘)으로 해결?
- bfs
2) 코딩 설명
<내 풀이>
from collections import deque
import sys
m,n,h = map(int, sys.stdin.readline().rstrip().split())
he = [0, 0, 0, 0, 1, -1]
r=[-1, 1, 0, 0, 0, 0]
c=[0, 0, -1, 1, 0, 0]
tom=[]
for i in range(h) :
tom.append(list(list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(n)))
def bfs(q) :
global day
while q :
# for mm in tom:
# print(mm)
# print()
now = q.pop()
for nn in range(6) :
tmph = now[0]+he[nn]
tmpn = now[1]+r[nn]
tmpm = now[2]+c[nn]
if 0<=tmph<h and \
0<=tmpn<n and \
0<=tmpm<m:
if tom[tmph][tmpn][tmpm]==0 :
tom[tmph][tmpn][tmpm]=now[3]+1
day=now[3]+1
q.appendleft((tmph, tmpn, tmpm, now[3]+1))
# 정수 1은 익은 토마토, 정수 0 은 익지 않은 토마토,
# 정수 -1은 토마토가 들어있지 않은 칸
q=deque()
blank=0 # -1 인 사과 세기용 (토마토 다 익었는지 여부 검사 위해)
for i in range(h) :
for j in range(n) :
for k in range(m) :
if tom[i][j][k]==1 :
q.append((i,j,k,0))
elif tom[i][j][k]==-1 :
blank+=1
# 토마토가 익어있는 상태이면 0
if len(q)+blank==m*n*h : print(0);exit()
day=0
bfs(q)
# q가 없어져서 끝났는데, tom 안에 0이 있다 => -1 출력
for i in range(h) :
for j in range(n) :
for k in range(m) :
if tom[i][j][k]==0 :
print(-1);exit()
else : print(day)
<내 틀렸던 풀이, 문제점>
시간 초과! ~ ! (지극히 당연 ㅋ)
from collections import deque
import sys
m,n,h = map(int, sys.stdin.readline().rstrip().split())
tom=[]
for i in range(h) :
tom.append(list(list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(n)))
# for mmm in tom :
# print(mmm)
# print()
# 정수 1은 익은 토마토, 정수 0 은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸
# 상 하 좌 우 & if tom[i-1] tom[i-1][r][c] * tom[i+1][r][c]
r=[-1, 1, 0, 0]
c=[0, 0, -1, 1]
def bfs(i,j,k):
# 익은 토마토 만나면 bfs 돌려서 0 인 아이들을 1로 만들어주기
q=deque()
q.append((i,j,k))
visited=[]
for i in range(h) :
visited.append(list([0]*m for _ in range(n)))
visited[i][j][k]=1
while q :
now = q.pop()
# print(q)
for i in range(4) :
tmpr = now[1]+r[i]
tmpc = now[2]+c[i]
if 0<=tmpr<n and 0<=tmpc<m and \
visited[now[0]][tmpr][tmpc]==0:
visited[now[0]][tmpr][tmpc]=1
if tom[now[0]][tmpr][tmpc]==0:
tom[now[0]][tmpr][tmpc]=-day
if tom[now[0]][tmpr][tmpc]==1:
q.appendleft((now[0], tmpr, tmpc ))
if 0<=now[0]-1 and visited[now[0]-1][now[1]][now[2]] ==0 :# and\
visited[now[0]-1][now[1]][now[2]] = 1
if tom[now[0]-1][now[1]][now[2]]==0:
tom[now[0]-1][now[1]][now[2]]=-day
if tom[now[0]-1][now[1]][now[2]]==1:
q.appendleft((now[0]-1, now[1], now[2]))
if now[0]+1<h and visited[now[0]+1][now[1]][now[2]] ==0 :#and\
visited[now[0]+1][now[1]][now[2]] = 1
if tom[now[0]+1][now[1]][now[2]]==0:
tom[now[0]+1][now[1]][now[2]]=-day
if tom[now[0]+1][now[1]][now[2]]==1:
q.appendleft((now[0]+1, now[1], now[2]))
# 1) 토마토가 0인 아이 없다면 다 익은 상황 , 모든 토마토 다 익은 것
tomato = False
for i in range(h) :
if tomato : break
for j in range(n) :
if tomato : break
for k in range(m) :
if tom[i][j][k]==0 :
tomato=True
break
if tomato==False:
#한번이라도 토마토가 true 되면 stop, 한번도 true 못 만나면 안 익은게 하나도 없는 것
print(0); exit()
# 2) 토마토가 다 익지 못하는 상황 존재 가능 (-1) => 0인 아이들 상하좌우 위 아래 검사
apple=[0,1]
tomato = False
for i in range(h) :
if tomato : break
for j in range(n) :
if tomato : break
for k in range(m) :
if tom[i][j][k]==0 : # 안 익은 사과 주변 6방향 모두 -1 인 경우라면 당장 exit 하고 -1 출력
chk=0 #chk 주변에 하나라도 1,0이 없으면 익기 불가
for p in range(4) :
tmpr = i+r[p]
tmpc =j+c[p]
if \
0<=tmpr<n and 0<=tmpc<m and \
tom[i][tmpr][tmpc] in apple :
chk=1
if 0<=i-1 and \
tom[i-1][j][k]in apple : chk=1
if i+1<h and \
tom[i+1][j][k]in apple : chk=1
if chk==0 : print(-1); exit()
# 3) 1,2 아니면 탐색 시작 ~
tomato = True
day = 0
while tomato :
# print(day)
day+=1
q=deque()
for i in range(h) :
for j in range(n) :
for k in range(m) :
if tom[i][j][k]==1 :
bfs(i,j,k)
# for mm in tom :
# print(mm)
tomato = False
#print(h,n,m)
for i in range(h) :
for j in range(n) :
for k in range(m) :
# print(i,j,k, end=" ")
# print(tom[i][j][k])
if tom[i][j][k]==0 :
tomato=True
elif tom[i][j][k]==-day : #익음 처리된 토마토 익게 해주기
#print("change eeeeeeeeee")
#print(tom[i][j][k])
tom[i][j][k]=1
#tomato=False
if tomato==False:
#한번이라도 안 익은 토마토(0)가 발견되면 stop,
# 한번도 true 못 만나면 익은게 하나도 없는 것
print(day); exit
질문 참고
https://www.acmicpc.net/board/view/86220
<반성 점>
<배운 점>
- 파이썬 프로그램 아예 종료 => exit() ; 괄호까지 필수!
