[백준] 7576.토마토/Python - Gold5

❓문제

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

성능 요약

코드1 ➡️ 메모리: 156792 KB, 시간: 460 ms
코드2 ➡️ 메모리: 228982 KB, 시간: 448 ms

 

문제 설명

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다.

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

✍🏻풀이

BFS 문제이다.

익지 않은 토마토는 익은 토마토의 영향을 받아 익는다. 익은 토마토는 오른쪽, 왼쪽, 앞, 뒤에만 영향을 줄 수 있다.
그러므로 테스트 케이스 2와 같이 (0, 0)에 위치한 토마토는 주위에 익은 토마토가 없으므로 익을 수 없다.
먼저 출발지를 찾기 위해 익은 토마토의 위치를 큐에 기록한다.
익은 토마토를 기점으로 오른쪽, 왼쪽, 앞, 뒤를 확인한다. 이 때, 아직 익지 않은 토마토라면 현재 토마토를 기점으로 +1을 한다.
boxes를 확인했을 때 익지 않은 토마토가 있다면 -1을 출력하고 이외에는 최소 날짜를 출력한다.

💻코드

코드 1

import sys
from collections import deque

input = sys.stdin.readline

n, m = map(int, input().split())
boxes = [list(map(int, input().split())) for _ in range(m)]
dir = [[1, 0], [-1, 0], [0, 1], [0, -1]]
q = deque()

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

def bfs():
    res = 0
    while q:
        y, x = q.popleft()
        for d in dir:
            ny, nx = y + d[0], x + d[1]
            if 0 <= ny < m and 0 <= nx < n:
                if boxes[ny][nx] == 0:
                    boxes[ny][nx] = boxes[y][x] + 1
                    q.append((ny, nx))

    for i in range(m):
        for j in range(n):
            if boxes[i][j] == 0:
                return -1
            res = max(res, boxes[i][j])

    return res - 1


print(bfs())

코드 2

import sys
from collections import deque

input = sys.stdin.readline

n, m = map(int, input().split())
boxes = [list(map(int, input().split())) for _ in range(m)]
dir = [[1, 0], [-1, 0], [0, 1], [0, -1]]
q = deque()

for i in range(m):
    for j in range(n):
        if boxes[i][j] == 1:
            q.append((i, j, 0))

def bfs():
    res = 0
    while q:
        y, x, day = q.popleft()
        for d in dir:
            ny, nx = y + d[0], x + d[1]
            if 0 <= ny < m and 0 <= nx < n:
                if boxes[ny][nx] == 0:
                    boxes[ny][nx] = 1
                    q.append((ny, nx, day + 1))
                    res = max(res, day + 1)

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

    return res


print(bfs())

📍후기

이 정도면 심각한 난독아닌가 싶다..그림을 그리면서 이건 bfs인데 어떻게 dfs이지 생각하면서 문제는 내 눈이다. bfs를 dfs로 읽고 이걸 dfs로 풀려고 했다. 아침부터 풀려니까 잠이 덜 깼나..

코드 1은 토마토가 담겨있는 상자를 그대로 이용하여 날짜를 기록하였다. 그리고 for문을 돌며 토마토가 모두 익을 때까지 걸리는 날짜를 구한다. 이 때, n * m번 max 함수를 반복하기 때문에 while에 계산하는 게 어떨까 생각했다. 그게 바로 코드2이다.

코드 2는 익지 않은 토마토라면 이를 1로 바꿔 익음을 표시하고 큐에 다음 상자 위치를 기록할 때 날짜와 함께 기록하고 이 때, 날짜를 갱신한다. 그렇기에 시간은 코드1에 비해 줄어들지만 메모리는 조금 더 차지하게 된다.