[BOJ ]7576. 토마토

문제

토마토 (https://www.acmicpc.net/problem/7576)

풀이

1. 초기 접근

• 문제조건 해석
  • 움직임, 경로에 대한 문제고, 간선의 길이가 1로 정해져있다.
    • BFS 문제다.
• 알고리즘
  • 가장 기초적인 BFS 문제라고 생각된다.
• 코드

import sys
from collections import deque

dxs = [-1, 0, 1, 0]
dys = [0, -1, 0, 1]

m, n = map(int, sys.stdin.readline().split())
board, q, visited = [], deque(), set()

for _ in range(n):
    board.append(list(map(int, input().split())))

for i in range(n):
    for j in range(m):
        if board[i][j] == 1:
            q.append((i, j))
            visited.add((i, j))

def bfs():
    step = 0
    while q:
        size = len(q)

        for i in range(size):
            x, y = q.popleft()

            for dx, dy in zip(dxs, dys):
                nx, ny = x + dx, y + dy
                if nx >=0 and nx < n and ny >= 0 and ny < m and \
                    (nx, ny) not in visited and board[nx][ny] != -1:
                    visited.add((nx, ny))
                    q.append((nx, ny))
                    board[nx][ny] = 1
        step += 1

    for i in range(n):
        for j in range(m):
            if board[i][j] == 0:
                return -1
    return step - 1

print(bfs())

2. 유의사항

• 초기 코드 (여기에는 없다.) 에는 q 를 deque 가 아닌 일반 list 를 사용했었다.
  즉, q = [] 였고, pop 할 때도, x, y = q.pop(0) 식으로 사용했었다.
• 근데 이러면 시간초과가 뜬다.
  이유는 q.pop(0) 에는 O(n) 만큼 시간이 걸린다. 나도 몰랐는데, 아무튼 연산시간이 그렇다.
• 반면 deque.leftpop() 에는 O(1) 만큼 시간이 걸린다. 매우매우 차이가 크다.
  이게 사람들이 파이썬에서 queue 를 쓸 때, list 를 안쓰고 deque 를 사용하는 이유다.
• 파이썬에서 queue 가 필요하면 무조건 deque를 사용하자.

파이썬 내장 함수의 시간복잡도

<https://daimhada.tistory.com/56