[백준] 7576번: 토마토

https://www.acmicpc.net/problem/7576

initial

It wasn't that hard considering it was Gold 5. But I was looking at how to count the actual number of days for everything to be ripe.

I thought about marking each grid with the cost and iterating through the changed graph and getting the maximum value. But I tried this way

        if 0<=next_x<row and 0<=next_y<col and not visited[next_x][next_y]:
            if graph[next_x][next_y]==-1 or graph[next_x][next_y]==1:
                continue
            queue.append((next_x,next_y,cur_cost+1))
            ans = max(ans, cur_cost+1)

I declared an ans variable and updated with the new cost each time an element from queue is done with BFS. Eventually, ans variable will contain the maximum cost, which represents the total number of days.

Also, I don't need this graph[next_x][next_y]==1 in my bfs because I have already added those in my queue before my bfs.

my correct solution:

from collections import deque

col, row = map(int,input().split())
graph = [list(map(int, input().split())) for _ in range (row)]
visited = [[False for _ in range(col) ] for _ in range(row)]
moves=[[1,0],[-1,0],[0,1],[0,-1]]
queue =deque()
ans=0
for i in range(row):
    for j in range(col):
        if graph[i][j]==1:
            queue.append((i,j,0))
            visited[i][j]=True
while queue:
    cur_x,cur_y,cur_cost=queue.popleft()
    for move in moves:
        next_x,next_y = move[0]+cur_x, move[1]+cur_y
        if 0<=next_x<row and 0<=next_y<col and not visited[next_x][next_y]:
            if graph[next_x][next_y]==-1 or graph[next_x][next_y]==1:
                continue
            queue.append((next_x,next_y,cur_cost+1))
            ans = max(ans, cur_cost+1)
            visited[next_x][next_y]=True
flag = False
for i in range(row):
    for j in range(col):
        if not visited[i][j] and graph[i][j]==0:
            flag = True
            break
if flag:
    print(-1)
else:
    print(ans)

Notice I used boolean flag for this implementation.

model ans from google

The answer online marked each grid with the new cost and iterated the graph one more time to get the maximum cost. You minus one because of the way this bfs is implemented. Not sure why though. tbc

tbc Oh we start from cost =1 because tomato value itself is 1.

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

m, n = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]
q = deque()

for i in range(n):
    for j in range(m):
        if arr[i][j] == 1:
            # 익은 토마토(1)의 좌표를 큐에 저장
            q.append([i, j])

dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]
while q:
    x, y = q.popleft()
    for i in range(4):
        # 익은 토마토 상하좌우 돌면서 일수 저장
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < n and 0 <= ny < m:
            if arr[nx][ny] == 0:
                arr[nx][ny] = arr[x][y] + 1
                q.append([nx, ny])

ans = 0
for line in arr:
    for tomato in line:
        if tomato == 0:
            # 안익은 토마토(0)이 있으면 바로 정지
            print(-1)
            exit()
    ans = max(ans, max(line))
# 1에서 시작했기 때문에 결과 값에서 1빼주기
print(ans-1)

complexity

The given code appears to be solving a problem related to finding the maximum distance (number of steps) between cells in a grid. Here's the complexity analysis:

1. Space Complexity:

   • The graph list is used to store the grid, which takes up O(row * col) space.
   • The visited matrix is used to keep track of visited cells in the grid, and it also takes up O(row * col) space.
   • The queue is a deque used for BFS, and it can contain at most O(row * col) elements.
   • Other variables (cur_x, cur_y, cur_cost, moves, ans, and flag) take constant space.

   The overall space complexity is O(row * col).

2. Time Complexity:

   • The code starts by iterating through the entire grid to find the initial positions with a value of 1 (land). This takes O(row * col) time.
   • Then, it performs a breadth-first search (BFS) on the grid. In the worst case, it explores all cells in the grid once, and for each cell, it performs constant-time operations.
   • The BFS operation dominates the time complexity, and since it explores each cell at most once, the time complexity is O(row * col).

The code efficiently finds the maximum distance between cells using BFS, and both its time and space complexity are O(row * col).