[백준] 7576번: 토마토 (파이썬)

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

 

전에 풀었던 bfs 문제들과 비슷한 문제였다.

전 문제들하고 비슷하게 입력받는 리스트, 방문 여부를 확인하는 visited 리스트 두개로 나눠서 풀려고 했다가 1%에서 계속 틀렸다고 해서 결국 다른 사람들의 코드를 참고했다 ㅠ

bfs에서 꼭 방문 리스트를 만들지 않아도 입력 받는 리스트를 조작해서 결과를 도출해도 된다는 사실을 알았다.

from collections import deque

cols, rows = map(int,input().split())
matrix = [list(map(int,input().split())) for _ in range(rows)]
queue = deque([])

#matrix를 돌면서 1의 위치를 queue에 추가
for i in range(rows):
    for j in range(cols):
        if matrix[i][j] == 1:
            queue.append((i,j))

def bfs(matrix, queue, rows, cols):
    directions = [(-1,0),(0,1),(1,0),(0,-1)] #시계방향
    while queue: #queue가 빌 때까지 반복
        curr_x, curr_y = queue.popleft()
        for i in range(4):
            next_x, next_y = curr_x + directions[i][0] , curr_y + directions[i][1]
            if 0<=next_x<rows and 0<=next_y<cols and matrix[next_x][next_y] == 0:
                matrix[next_x][next_y] = matrix[curr_x][curr_y] + 1
                queue.append((next_x,next_y))


bfs(matrix, queue, rows, cols)

for i in range(rows):
    print(matrix[i])

max_val = 0
for row in matrix: #각 행을 돌면서 0이 있나 확인
    if 0 in row:
        print(-1)
        exit()
    max_val = max(max_val, max(row)) #0이 없다면 최대값을 갱신
print(max_val - 1) #결과 출력

어제 풀다가 화나서 자고 일어나서 다시 풀었다..