[➕ 오답노트] 백준 7576번 배열 BFS

👇🏻 문제 

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

7576번: 토마토

---

배열 자료구조의 DFS는 많이 풀어봤지만, BFS는 처음이다.

그래서 못 풀었다 ㅎ

 

import sys
from collections import deque

M, N = map(int, sys.stdin.readline().strip().split())
tomato = [list(map(int, sys.stdin.readline().strip().split())) for _ in range(N)]

q = deque([])
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]

for i in range(N):
    for j in range(M):
        if tomato[i][j] == 1:
            q.append([i, j])

def BFS():
    while q:
        row, col = q.popleft()
        for i in range(4):
            nx, ny = dx[i] + row, dy[i] + col
            if 0 <= nx < N and 0 <= ny < M and tomato[nx][ny] == 0:
                tomato[nx][ny] = tomato[row][col] + 1
                q.append([nx, ny])

BFS()
cnt = 0

for i in tomato:
    for j in i:
        if j == 0:
            print(-1)
            exit(0)
    cnt = max(cnt, max(i))

print(cnt - 1)

 

큐를 이용해 문제를 풀 때, from queue import Queue를 주로 쓰는데 시간초과가 난다는 얘기가 있어서 deque를 쓰기로 했다. deque의 popleft는 시간복잡도가 O(1)임.

 

이 문제에서 내가 놓쳤던 부분은 방향 배열을 사용하는 것이다. 

또한, visited 배열을 따로 만들 필요 없이 배열의 값을 변경(+1 이라던가)하면 1일 때 감지하지 않는다.

 

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

def BFS():
    while q:
        row, col = q.popleft()
        for i in range(4):
            nx, ny = dx[i] + row, dy[i] + col
            if 0 <= nx < N and 0 <= ny < M and tomato[nx][ny] == 0:
                tomato[nx][ny] = tomato[row][col] + 1
                q.append([nx, ny])

 

dx,dy를 선언하고 추출한 q의 첫번째 원소에 x,y를 더해 사용하면 된다.

인덱스 에러가 날 가능성이 매우 높으니 범위를 설정해주어 에러를 처리하면 된다. 

 

방향 배열은 종종 사용되니 기억해두자 아자아자 수요일 화이팅

오늘도 코테 2개 떨어짐 (⁄ ⁄•⁄ω⁄•⁄ ⁄)⁄  (사실 어제)