bj7576 토마토

우선 문제를 보자마자 BFS 문제라는 것을 파악함.
근데 내가 문제를 너무 어렵게 생각했다...
그래서 풀면서도 이게 골드 5라고? 이러면서 풀었음 ㅋㅋ

📌 처음 생각
음... 토마토의 위치를 모두 파악해서 그것을 어떤 복합타입으로 저장한 후 한 토마토의 BFS를 진행하면 flag = False로 지정해서 loop가 돌아가지 않도록 하고 다른 복합타입의 flag는 True로 지정해주어서 한 번씩 돌아가도록 순서를 맞추어 주었다.

📌 나중 생각
근데 계속 넣어줘야하는 조건들이 추가되었고 조건이 많이 추가되다보니 이렇게 푸는 것이 아니라는 생각이 들어서 다시 한번 생각해보니 어차피 Queue에 그냥 넣으면 순서를 지켜서 BFS하게 된다는 것을 파악함. 그래서 싹 다 지우고 다시 시작함ㅋㅋㅋㅋㅋㅋㅋㅋ

📌 SOLVING
1. BFS 사용.
2. 탐색한 2차원 리스트 배열의 값을 하나씩 증가시키면 따로 cnt 변수를 사용하지 않아도 된다.
3. 마지막으로 loop를 쫙 돌면서 익지 않은 토마토에 대한 예외처리를 해주고 각 list의 최댓값을 파악해서 출력해준다.

from collections import deque

n, m = map(int, input().split())
card = []
tmt = []
def isvalid(graph ,row ,col):
    if row < 0 or row >= m:
        return False
    if col < 0 or col >= n:
        return False
    if graph[row][col] != 0:
        return False
    return True


def bfs(graph, flag):
    queue = deque([])
    for i in range(len(flag)):
        row = flag[i][0]
        col = flag[i][1]
        queue.append([row, col])

    move = [(-1,0),(1,0),(0,-1),(0,1)]
    while queue:
        x, y = queue.popleft()

        for j in range(4):
            nx = x + move[j][0]
            ny = y + move[j][1]
            if isvalid(graph, nx, ny):
                queue.append([nx, ny])
                graph[nx][ny] = graph[x][y] + 1



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

for i in range(m):
    for j in range(n):
        if card[i][j] == 1:
            tmt.append([i, j])
bfs(card, tmt)
cnt = 0
for i in card:
    for j in i:
        if j == 0:
            print(-1)
            exit(0)
    cnt = max(cnt, max(i))
print(cnt - 1)