[백준] 7576번 토마토, BFS, deque

문제 설명

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

나의 첫 번째 풀이

기존에 풀던대로 list를 queue처럼 사용하여 문제를 풀었을 때에는 시간초과가 났다. list의 pop(0)을 사용하면 index=0인 값이 list에서 pop 되는데 이는 O(n)의 시간 복잡도를 가진다.

O(1)의 시간복잡도를 가지는 deque를 사용하면 시간초과 문제는 해결된다. deque에 대한 정리는 여기서 하겠다.

import sys
from collections import deque

N, M = map(int, sys.stdin.readline().split())

matrix = list()
queue =  deque()

for i in range(M): 
    input_map = list(map(int, sys.stdin.readline().split()))
    matrix.append(input_map)
    for j in range(N): 
        if matrix[i][j] == 1:
            queue.append([i, j])

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

days = [[0]*N for _ in range(M)]

def bfs():
    visited = [[0]*N for _ in range(M)]

    while queue:
        for _ in range(len(queue)):
            i, j = queue.popleft() 

            for direction in range(4):
                goX = i + dx[direction]
                goY = j + dy[direction]

                if goX>= 0 and goX < M and goY >= 0 and goY < N and visited[goX][goY] == 0 and matrix[goX][goY] == 0:
                    matrix[goX][goY] = 1
                    visited[goX][goY] = 1
                    days[goX][goY] = days[i][j] + 1
                    queue.append([goX, goY])

bfs()

ans = max(map(max, days))

bool = True
for i in range(M):
    if 0 in matrix[i]:
        bool = False

if bool:
    print(ans)
else:
    print(-1)

풀고 나니 visited를 꼭 체크해야 하나 싶었다. 왜냐하면 matrix에서 0인 부분을 찾아 bfs를 진행하는 로직이고, 한번이라도 지나가면(지나갈 수 없는 부분 제외) 1이 되니 자동으로 visited 체크가 될 수 있기 때문이다.

또한, bfs() 함수에서 while문 안에 queue의 길이만큼 반복문을 넣어줬는데, 이 또한 제거해도 되는 코드였다. 해당 반복문을 넣었던 이유는 초기 익은 토마토의 개수가 여러개일때를 생각해서 추가한 로직인데, 전혀 필요 없는 로직이었다.

나의 두 번째 풀이

아래는 위의 코드를 간소화한 코드이다.

import sys
from collections import deque

N, M = map(int, sys.stdin.readline().split())

matrix = list()
queue =  deque()

for i in range(M):
    input_map = list(map(int, sys.stdin.readline().split()))
    matrix.append(input_map)
    for j in range(N): # 입력받은 그래프에 이미 익은 (1) 토마토의 좌표를 queue에 저장
        if matrix[i][j] == 1:
            queue.append([i, j])

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

# 익은 날짜를 저장할 배열. 가장 큰 날짜를 구하는 게 이 문제의 정답이다.
days = [[0]*N for _ in range(M)]

def bfs():
    while queue:
        i, j = queue.popleft() # pop(0)과 같음. deque의 메소드

        for direction in range(4):
            goX = i + dx[direction]
            goY = j + dy[direction]

            if goX>= 0 and goX < M and goY >= 0 and goY < N and matrix[goX][goY] == 0:
                matrix[goX][goY] = 1
                days[goX][goY] = days[i][j] + 1
                queue.append([goX, goY])

bfs()
# 이차원 배열의 최대값
ans = max(map(max, days))

# 익지 않은(0) 토마토가 있을 시에는 -1을 리턴, 그렇지 않으면 최대 일수를 리턴
bool = True
for i in range(M):
    if 0 in matrix[i]:
        bool = False

if bool:
    print(ans)
else:
    print(-1)