[백준] 7576번 토마토 파이썬(python) 풀이

안녕하세요? 닉네임간편입니다. 이번 시간에는 토마토 문제를 풀어보겠습니다.

[문제 링크]

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

7576번: 토마토

1. 접근 방식

우선 이 문제에서 요구하는 것이 주어진 토마토가 모두 익을 수 있는 최소 일수를 구하는 것이므로, 너비 우선 탐색(BFS)으로 접근하면 되겠습니다.

또한 익은 토마토는 인접한 익지 않은 토마토를 익게 하기 때문에, 상하좌우 방향키처럼 토마토를 익게 하면서 모든 토마토를 익게 하는 데 걸리는 기간을 구하면 되겠습니다.

2. 전체 코드

from collections import deque
import sys
input = sys.stdin.readline

M, N = map(int, input().split())
box, ripe, want = [], deque(), M*N
for i in range(N):
    box.append(list(map(int, input().split())))
    for j in range(M):
        if box[i][j] == 1:
            ripe.append((i, j))
        elif box[i][j] == -1:
            want -= 1


def bfs(total, want):
    cnt = 0
    while ripe:
        if total == want:
            return cnt
        cnt += 1
        for _ in range(len(ripe)):
            y, x = ripe.popleft()
            for m in ((0,1), (1,0), (0,-1), (-1,0)):
                ny, nx = y + m[0], x + m[1]
                if 0 <= ny < N and 0 <= nx < M and box[ny][nx] == 0:
                    ripe.append((ny, nx))
                    box[ny][nx] = 1
                    total += 1
    return -1


print(bfs(len(ripe), want))

우선 전체 코드는 다음과 같습니다. 아래에 좀 더 자세히 살펴보겠습니다.

3. 코드 분석

1) 입력받기 및 필요한 변수, 배열 생성

from collections import deque
import sys
input = sys.stdin.readline

M, N = map(int, input().split())
box, ripe, want = [], deque(), M*N
for i in range(N):
    box.append(list(map(int, input().split())))
    for j in range(M):
        if box[i][j] == 1:
            ripe.append((i, j))
        elif box[i][j] == -1:
            want -= 1

 

a) box, ripe, want

먼저 토마토가 있는 상자 배열을 box로 선언해 생성합니다. 

그리고 익은 토마토에 대해서 처리를 해주어야 하는데, 이때 bfs() 메서드에서 덱을 생성하는 것보다 초기에 미리 생성한 후 익은 토마토의 좌표를 넣어놓는 것이 낫다고 판단하여 여기에 생성했습니다.

want 변수는 모든 토마토의 개수로, 익어야 할 목표 토마토 수입니다.

b) box[i][j] == 1, box[i][j] == -1 처리

만일 토마토 상자 배열에서 1로 표시된 값이 있다면, 즉 익은 토마토가 있다면 해당 좌표를 ripe 덱에 넣습니다.

만일 상자 배열에서 -1로 표시된 값이 있다면, 즉 토마토가 있지 않은 공간이 있다면 해당 공간의 수만큼 목표 토마토 수가 감소하므로 want를 1 감소시킵니다.

2) bfs() 함수

def bfs(total, want):
    cnt = 0
    while ripe:
        if total == want:
            return cnt
        cnt += 1
        for _ in range(len(ripe)):
            y, x = ripe.popleft()
            for m in ((0,1), (1,0), (0,-1), (-1,0)):
                ny, nx = y + m[0], x + m[1]
                if 0 <= ny < N and 0 <= nx < M and box[ny][nx] == 0:
                    ripe.append((ny, nx))
                    box[ny][nx] = 1
                    total += 1
    return -1

 

a) total, want, cnt

우선 현재 익은 토마토 수와 목표 토마토 수를 파라미터로 전달받습니다. 이후 기간에 해당하는 cnt 변수를 0으로 초기화하고, while문에서 반복을 진행할 때마다 1을 추가합니다.

b) while문

ripe 덱에 요소가 있을 때까지 동작을 반복합니다.

만일 현재 익은 토마토 수가 목표 토마토 수와 일치한다면, 현재 cnt를 반환합니다.

그렇지 않다면, cnt에 1을 추가한 후 다음 동작을 수행합니다.

만일 덱에 요소가 없음에도 아직 cnt가 반환되지 않았다면, 즉 모든 익은 토마토가 인접한 토마토를 익게 했음에도 불구하고 존재하는 모든 토마토를 익게 하지 못했다면(total!= want), -1을 반환하도록 합니다.

c) for _ in range(len(ripe))

동작을 함에 앞서 현재 ripe 덱의 길이만큼만 반복합니다.

이렇게 하는 이유는 현재 덱에 있는 익은 토마토들만 인접한 익지 않은 토마토를 익게할 수 있고, 이때 익은 토마토들은 다음 날이 되어야 다른 토마토를 익게 할 수 있기 때문입니다.

d) 인접한 토마토 익히기

먼저 덱에서 y, x 좌표를 꺼냅니다.

그리고 각각 상하좌우 별로 좌표를 움직이며 만일 해당 좌표가 배열 범위 내에 있고, 토마토 상자 배열에서 그 좌표의 값이 0이라면, 즉 아직 익지 않은 토마토라면 다음 동작을 수행합니다.

a) ripe 덱에 넣기

b) 토마토 상자 배열에서 해당 좌표 값 1로 설정하기(익게 하기)

c) 총 익은 토마토 수 1 추가하기

3) 출력

print(bfs(len(ripe), want))

마지막으로 bfs() 함수를 통해 구한 값을 출력합니다.

3. 마무리

파이썬으로 풀어본 토마토 문제였습니다. 비록 완벽한 풀이는 아니겠지만 그래도 알고리즘 초심자로서 성공했다는 것에 의의를 두는... 닉네임간편이었습니다.

혹시 궁금하신 점이 있으시다면 부담 없이 댓글로 남겨주시길 바랍니다.