[백준] 7576번 : 토마토

 

 

 

 

 

 

 

접근법

- 일반적인 dfs 방식으로 풀어보려다가 내가 잘못한 건지 몰라도 재귀를 돌리다 보니 원하는 결과 값을 얻질 못해서 bfs 방식으로 접근을 했다.

 

- queue를 만들고 matrix에서 1인 부분을 queue에 넣어준다.

 

- queue에서 가장 앞에 있는 것을 빼서 row(행), col(열)에 저장을 한다.

 

- 현재 픽셀을 기준으로 상, 하, 좌, 우에 visit[n_row][n_col]이 0이고, matrix[n_row][n_col]이 -1이 아니라면 그 픽셀을 현재 방문하고 있는 픽셀의 값 + 1을 넣어준다.(하루가 지나갔기 때문에 + 1) 그 후 그 픽셀 이후 값들을 검사하기 위해 [n_row, n_col]을 queue에 넣어준다.

 

- 위의 경우 행이 0보다 작거나 전체 row크기보다 커지면 안되므로, 0 <= n_row < N and 0 <= n_col < M 조건을 만족시키는 경우에만 돌려준다.

 

- 처음에 queue를 리스트로 지정을 하고 돌렸더니 시간 초과가 발생했다. deque를 사용하면 입출력 속도가 빨라서 그런지 시간을 줄일 수 있다고 해서 deque를 import하고 했더니 성공했다.

 

 

 

 

 

 

 

풀이

from collections import deque

M, N = map(int, input().split())
matrix = list()
for _ in range(N) :
    matrix.append(list(map(int, input().split())))

visit = matrix

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

queue = deque()

def check(matrix):
    max_val = 0
    for i in range(N) :
        for j in range(M) :
            if matrix[i][j] == 0:
                return -1
                break
            else :
                if matrix[i][j] > max_val :
                    max_val = matrix[i][j]
    return max_val - 1

for i in range(N) :
    for j in range(M) :
        if matrix[i][j] == 1 :
            queue.append([i, j])
            
while queue :
    row, col = queue.popleft()
    for i in range(4) :
        n_row = row + dx[i]
        n_col = col + dy[i]
        if 0 <= n_row < N and 0 <= n_col < M :
            if visit[n_row][n_col] == 0 and matrix[n_row][n_col] != -1 :
                visit[n_row][n_col] = visit[row][col] + 1
                queue.append([n_row, n_col])

print(check(visit))

 

 

 

 

 

 

 

결과