[백준 BOJ] 7576 : 토마토 - python

SUN·2022년 9월 7일

BFS boj python 백준 알고리즘

algorithm

목록 보기

14/30

오늘 풀어볼 문제는 토마토 이다.

문제

풀이 과정

뭔가 상하좌우로 탐색해서 최소를 구해야 하는 문제다.
'탐색'을 해서 '최소'를 구한다.
여기서부터 BFS의 냄새가 났다.
그리고 경험상 이렇게 행렬에서 상하좌우로 움직이는 문제는 BFS나 DFS 문제가 많았다.

그래서 BFS로 풀면 되겠다고 생각했고, 어떻게 사용할까 생각을 하다가
토마토 위치 부터 시작해서 더이상 익힐 토마토가 없을 때 까지 bfs를 쭉 해보면 되겠다라는 결론에 다다랐다.

내가 생각한 알고리즘은 다음과 같다.

처음에 주어진 안익은 토마토 개수를 센다.
(이 개수가 탐색을 끝낸 후 익힌 토마투 개수와 같으면 모두 익힐 수 있다는 뜻이므로
걸린 일수 출력, 아니면 -1을 출력하기 위해서)
처음부터 익어 있는 토마토 위치들을 모두 큐에 넣는다.
큐에서 하나씩 빼와서 주위에 안익은 토마토가 있으면 익히고 그 위치를 큐에 넣기를 큐가 빌 때 까지 반복한다.
처음에 주어진 안익은 토마토 개수가 탐색 후에 익혀진 토마토 개수와 같으면
그 때까지 걸린 일 수 출력하고 아니면 -1 출력한다.

나의 코드

from collections import deque
import sys

input = sys.stdin.readline

width, height = map(int, input().split())

tomatos = []

dq = deque()

# 안익은 토마토 개수
# 처음에 주어진 안익은 토마토 개수 탐색을 끝낸 후 익힌 토마토 개수가 같으면
# 모든 토마토를 익힐 수 있는 상황이니까 그 때 까지 걸린 일수를 출력
# 그게 아니라면 -1을 출력하기 위해
unripe_tomatos = 0
for i in range(height):

    numbers = []
    for j, number in enumerate(input().split()):
        number = int(number)
        numbers.append(number)

        # 익은 토마토면
        if number == 1:
            # 익은 토마토 위치부터 bfs로 탐색해야되니까 그위치를 큐에 넣음
            dq.append((i, j, 0))  # (익은 토마토의 행, 익은 토마토의 열, 현재 탐색 일수)

        # 안 익은 토마토면
        if number == 0:
            unripe_tomatos += 1

    tomatos.append(numbers)

# 상하좌우로 움직이기 위해
_dr = [0, 1, 0, -1]
_dc = [1, 0, -1, 0]

# 방문 정보를 저장
# 리스트로 하면 시간초과남(O(n)), dict로 찾는 게 훨씬 빠름 (O(1))
visited = {}

# 탐색을 통해 익혀진 토마토 개수
riped_tomatos = 0
# 최소 일 수
min_days = 0

while dq:
    r, c, days = dq.popleft()  # 행, 열, 현재 일 수

    for dr, dc in zip(_dr, _dc):  # 상하좌우로 움직여봄
        nr = r + dr
        nc = c + dc

        # 다음 좌표가 범위를 벗어나면 신경안씀
        if nr < 0 or nc < 0 or nr >= height or nc >= width:
            continue

        # 다음 좌표의 토마토가 익지 않았고 탐색되지 않은 토마토면
        if tomatos[nr][nc] == 0 and (nr, nc) not in visited:
            # 익혀진 토마토 개수 1증가
            riped_tomatos += 1

            # 방문 정보 저장
            visited[(nr, nc)] = 1

            # 다음 좌표와 현재 일 수를 +1해서 큐에 저장
            dq.append((nr, nc, days + 1))

    # 큐가 빌 때 마지막에 나온 days가 최소 일 수 일 것
    # 그러니까 min_days값은 days로 계속 갱신해주면 됨
    min_days = days

# 처음에 안익은 토마토 개수가 탐색으로 익혀진 토마토 개수와 같으면 min_days 출력
if unripe_tomatos == riped_tomatos:
    print(min_days)

# 아니면 다 익히지 못한다는 거니까 -1 출력
else:
    print(-1)

결과는 통과

다른 사람의 풀이

from collections import deque

m, n = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(n)]
queue = deque([])
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
res = 0

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

def bfs():
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx, ny = dx[i] + x, dy[i] + y
            if 0 <= nx < n and 0 <= ny < m and matrix[nx][ny] == 0:
                matrix[nx][ny] = matrix[x][y] + 1
                queue.append([nx, ny])

bfs()
for i in matrix:
    for j in i:
        if j == 0:
            print(-1)
            exit(0)
    res = max(res, max(i))
print(res - 1)