[알고리즘] 백준 7576 : 토마토 - G5

문제

2023.07.27 풀이

정답풀이

import sys
input=sys.stdin.readline
from collections import deque

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

m,n=map(int, input().split())
for _ in range(n):
    arr.append(list(map(int, input().split())))

queue=deque()

for i in range(n):
    for j in range(m):
        if arr[i][j]==1:
            queue.append((i,j))

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

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

        if nx<0 or nx>=n or ny<0 or ny>=m:
            continue
        if arr[nx][ny]==0:
            arr[nx][ny]=arr[x][y]+1
            queue.append((nx,ny))

k=max(map(max, arr))-1
for i in arr:
    if 0 in i:
        k=-1
        break
print(k)

---

첫 풀이

def bfs(i,j):
    queue=deque()
    queue.append((i,j))
    while queue:
        x,y=queue.popleft()

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

            if nx<0 or nx>=n or ny<0 or ny>=m:
                continue
            if arr[nx][ny]==0:
                arr[nx][ny]=arr[x][y]+1
                queue.append((nx,ny))
    return

for i in range(n):
    for j in range(m):
        if arr[i][j]==1:
            bfs(i,j)

# k= max(max(arr))-1
k=max(map(max, arr))-1

• "주변" 토마토가 하루에 한 칸씩 옮겨감 -> bfs로 판단

---

다른 풀이

while Q:
    x,y = Q.popleft()
    
    for mx,my in zip(mx_list,my_list):
        nx = x + mx
        ny = y + my
        if 0<=nx <N and 0<=ny<M and G[nx][ny]== 0  : # 익지 않았다면
            Q.append((nx,ny))
            G[nx][ny] = G[x][y]+1 # days +1

---

check point

• 2차원 배열에서의 가장 최댓값 구하는 쉬운 코드 : max(map(max, arr))
max(max(arr))는 arr의 행의 합이 가장 큰 행에서의 최댓값을 찾는 코드
  -> 정 생각 안나면 2중반복문이라도 쓰기

• 함수로 넘겨주는 것과 바로 큐에 저장하는 것의 차이.?!?!