7576 - 토마토

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

7576번: 토마토

 

 

- BFS

 

import sys
input = sys.stdin.readline

from collections import deque

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

q = deque()
for i in range(n):
    for j in range(m):
        if tomato[i][j] == 1:
            q.append([i,j])

delta = [(-1,0),(1,0),(0,-1),(0,1)]
predecessor = [[0] * m for _ in range(n)]

while len(q) != 0:
    r, c = q.pop()
    for i, j in delta:
        dr = r + i
        dc = c + j
        if 0 <= dr < n and 0 <= dc < m and tomato[dr][dc] == 0:
            tomato[dr][dc] = 1
            q.appendleft([dr,dc])
            predecessor[dr][dc] = predecessor[r][c] + 1

for i in range(n):
    for j in range(m):
        if tomato[i][j] == 0:
            print(-1)
            exit()

m = 0
for i in predecessor:
    k = max(i)
    if k > m:
        m = k

print(m)

 

BFS 문제의 정석, 토마토 문제를 풀었다!

요번에 백준 시작하고 처음 푼 골드 문제 ㅎㅎㅎ

 

그렇게 어렵지는 않다

큐에 원래 1이었던 정점을 넣어주고 똑같이 bfs 돌리면 된다

 

근데 이상하게 카운트를 어떻게 해야할지 모르겠어서.. 그림 그렸는데 그냥 저번에 미로 찾기 하던거랑 똑같이 predecessor 리스트 만들어주면 해결이었다~~

 

 

+) 실력이 마구마구 늘어나니 나중에는 CP도 해보고 싶다 Atcoder랑 Codeforces에서 ㅎㅎㅎ 이미 회원가입은 해놨다

++) 집에 종만북 책 사둔거 있었는데 예전에 읽다가 어려워서 포기했었다.. 근데 이제 한 번 도전해볼만 할듯ㅎ 다음주에 가져올 예정