백준 - 7576 토마토

백준 - BFS 7576번 토마토

문제)

1트로 실패한 코드)

from collections import deque
import multiprocessing

m,n = map(int,input().split())

graph =[]
for _ in range(n):
  graph.append(list(map(int,input().split())))

# 토마토 위치 저장
tomatos = []
for i in range(n):
  for j in range(m):
    if graph[i][j] == 1:
      tomatos.append((i,j))

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

def bfs(x,y):
  queue = deque()
  queue.append((x,y))

  while queue:
    x,y = queue.popleft()

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

      if nx <0 or ny <0 or nx >n-1 or ny >m-1:
        continue
      if graph[nx][ny] == -1:
        continue

      if graph[nx][ny] == 0:
        graph[nx][ny] == graph[x][y] +1
      if graph[nx][ny] > graph[x][y] :
        graph[nx][ny] == graph[x][y] +1
      queue.append((nx,ny))

for tomato in tomatos:
  bfs(tomato[0],tomato[1])


maex = - 5
for q in range(n):
  for w in range(m):
      if graph[q][w] == 0:
        print(-1)  
        k =0
      maex = max(maex,graph[q][w])

if k == 0:
  print(-1)
else:
  print(maex)
    

pypy로 성공한 코드)

from collections import deque


m,n = map(int,input().split())

graph =[]
for _ in range(n):
  graph.append(list(map(int,input().split())))


# 토마토 위치 저장
queue = deque()
for i in range(n):
  for j in range(m):
    if graph[i][j] == 1:
      queue.append((i,j))


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

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

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

      if nx <0 or ny <0 or nx >n-1 or ny >m-1:
        continue
        
      if graph[nx][ny] == -1:
        continue

      if graph[nx][ny] == 0:
        graph[nx][ny] = graph[x][y] +1     
        queue.append((nx,ny))




bfs()
maex = - 5
k = 1
for q in graph:
  for w in q:
    if w == 0: 
      k =0
      
    maex = max(maex,max(q))


if k == 0:
  print(-1)
else:  
  print(maex-1)

2트로 수정한 코드)

from collections import deque

m,n = map(int,input().split())
graph=[(list(map(int,input().split()))) for _ in range(n)]
queue = deque([])
dx, dy = [-1,1,0,0], [0,0,-1,1]
res  = 0

for i in range(n):
  for j in range(m):
    if graph[i][j] == 1:
      queue.append([i,j])
   
def bfs():
  while queue:
    x,y = queue.popleft()
    for i in range(4):
      nx, ny = x + dx[i], y + dy[i]
     
      if 0<=nx<n  and 0<=ny<m and graph[nx][ny] == 0:
        graph[nx][ny] = graph[x][y] +1     
        queue.append([nx,ny])
        
bfs()
for i in graph:
  for j in i:
    if j == 0: 
      print(-1)
      exit(0)
    res = max(res,max(i))

print(res-1)

성공한 나의 코드)

from collections import deque

m,n = map(int,input().split())
graph=[list(map(int,input().split())) for _ in range(n)]
queue = deque([])
dx, dy = [-1,1,0,0], [0,0,-1,1]
res  = 0


for i in range(n):
  for j in range(m):
    if graph[i][j] == 1:
      queue.append([i,j])
   
def bfs():
  while queue:
    x,y = queue.popleft()
    for i in range(4):
      nx, ny = x + dx[i], y + dy[i]
     
      if 0<=nx<n  and 0<=ny<m and graph[nx][ny] == 0:
        graph[nx][ny] = graph[x][y] +1     
        queue.append([nx,ny])
        
bfs()
for i in graph:
  for j in i:
    if j == 0: 
      print(-1)
      exit(0)
  res = max(res,max(i))

print(res-1)

comment) 이 문제 시간초과에서 힘들었다. 왜 구글링한답과 내답이 비슷한데 그 사람것은 되고 내 건 안되는지 주말 개인정비를 다버려가면서.... 라고하기엔 멍청한 실수여서 내 실력이 구데기인것으로 하자 ㅋㅋㅋㅋㅋㅋ. 답은 내장함수인 max를 첫 for 문에 들여놨어야 하는데 if문안에 아무생각없이 넣어놨다. max가 이중 포문에 조건문 안에 들어가있었으니 O(N^2)보다 오래 걸렸을 것이다. 필요없는데 조금 더 생각을 안하는 것으로 놓치는 코드 실수가 없었으면 좋겠다.....

또한 이때까지 푼 문제들은 첫 큐에 하나의 좌표만 넣는 것이였다. 근데 이번에는 시작점이 몇개일지 모르는 문제였다. 멀티프로세싱을 가지고 올려고도 했었고 .. 근데 정답은 간단했다. 그냥 큐에 시작점을 다 때려박으면 되는 것이였다. DEQUE도 리스트와 비슷하기 때문에 함수 외 내에서도 수정할 수 있는 것같다.