[김태원 알고리즘] 토마토 (BFS)

사용 언어: Python3

문제

백준에도 같은 문제가 있다.

풀이

내 풀이

from collections import deque

def countZero(board):
    cnt = 0
    for row in board:
        cnt += row.count(0)
    return cnt

M, N = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]

q = deque()
dx, dy = [0,-1,0,1], [1,0,-1,0]
ans = 0
flag = False # 토마토가 모두 익을 수 있는 상황인지
for i in range(N):
    for j in range(M):
        if board[i][j] == 1:
            q.append((i, j))
while q:
    if countZero(board) == 0:
        flag = True
        break
    for _ in range(len(q)):
        cur = q.popleft()
        for w in range(4):
            xx, yy = cur[0]+dx[w], cur[1]+dy[w]
            if xx<0 or xx>=N or yy<0 or yy>=M:
                continue
            if board[xx][yy] == 0:
                board[xx][yy] = 1
                q.append((xx, yy))
    ans += 1

print([-1, ans][flag])    

• 테스트 케이스는 통과하지만 백준에 제출했을 때는 시간초과가 발생한다

내 풀이 (dist 리스트 추가) - 0525 추가

# 10:06 ~
import sys
from collections import deque
input = sys.stdin.readline

M, N = map(int, input().rstrip().split())
board = [list(map(int, input().rstrip().split())) for _ in range(N)]

visited = [[0] * M for _ in range(N)]
dist = [[0] * M for _ in range(N)] # ✅ 각각의 토마토가 익는데까지 걸린 일수

q = deque()
for i in range(N):
    for j in range(M):
        if board[i][j] == 1:
            visited[i][j] = 1
            q.append((i, j))

dx, dy = [0,-1,0,1], [1,0,-1,0]
while q:
    x, y = q.popleft()
    for w in range(4):
        xx, yy = x+dx[w], y+dy[w]
        if xx<0 or xx>=N or yy<0 or yy>=M:
            continue
        if board[xx][yy] == 0 and not visited[xx][yy]:
            visited[xx][yy] = 1
            dist[xx][yy] = dist[x][y] + 1
            q.append((xx, yy))

flag = True
for i in range(N):
    for j in range(M):
        if visited[i][j] == 0 and board[i][j] != -1: # 토마토가 없느 곳이 아닌데 방문하지 않은 경우
            print(-1)
            flag = False # flag 업데이트
if flag:
    print(max(map(max, dist)))

• 정답!

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기