[bfs/백준] 7576번 : 토마토

- 문제 : https://www.acmicpc.net/problem/7576

 

문제 이해 

- 2차 행렬이 주어지는데 1은 토마토가 있는 곳, -1은 박스가 있어서 이동을 못하고, 0은 토마토가 있는 부분이다. 

- 토마토가 있는 1을 중심으로 상하좌우에 0인 지점들로 bfs를 진행하는 문제다. 

- 풀면서 헷갈렸던 부분이 처음에 1인 지점(토마토가 있는 지점)이 여러개 있을텐데 이게 어떻게 동시다발적으로 진행시키지?였다. 

좀 헤매다가 답을 보니 처음에 행렬이 주어질 때 1인 지점들을 미리 queue에 담아두었다가 그거를 중심으로 bfs를 진행하면 된다. 

 

풀이 로직

- 입력값 n, m, matrix를 저장하고 matrix를 입력받을 때 1인 지점은 따로 queue에 저장한다.

- bfs를 실행하는데 방문여부는 visit로, 토마토 개수는 matrix를 이용해서 기록한다. 

- bfs를 끝낸 뒤 행렬을 전체 탐색하면서 0인 지점(안 익은 토마토)이 있으면 실패이고, 없다면 전체 값 중에 최대값을 출력하면 된다.

실패 여부는 flag를 이용해서 matrix에서 0인 지점이 있다면 False 처리한다. 

- flag 값에 따라 값을 다르게 출력해준다.

 

정답 풀이 

이전에 풀 때는 엄청 쉬웠던 것 같은데 다시 풀려니까 쉽지않다^^;

from collections import deque

def bfs():
    dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
    while queue : 
        x, y = queue.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if not visit[nx][ny] and matrix[nx][ny] == 0:
                    visit[nx][ny] = 1
                    matrix[nx][ny] = matrix[x][y] + 1
                    queue.append([nx, ny])
                    
        
m, n = map(int, input().split())
matrix = []
queue = deque()
for i in range(n):
    matrix.append(list(map(int, input().split())))
    for j in range(m):
        if matrix[i][j] == 1:
            queue.append([i, j])


visit = [[0] * m for _ in range(n)]
bfs()
            
answer = 0
flag = True
for i in range(n):
    if 0 in matrix[i]:
        flag = False
        break
    else:
        answer = max(answer, max(matrix[i]))
        
if flag == True:    
    print(answer - 1)
else:
    print(-1)