[BOJ] 7576. 토마토

문제

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

 

• M * N 칸으로 이뤄진 상자에 토마토가 존재
• 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸
• 토마토가 모두 익을 때까지의 최소 날짜를 출력
  • 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력
  • 토마토가 모두 익지는 못하는 상황이면 -1을 출력

6 4 # M*N
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1

 

 

---

 

주요 아이디어

• 전형적인 BFS 문제
• 익은 토마토를 시작 좌표로 삼고 큐에 모조리 넣어놓자
• bfs를 진행하면서 box에다 며칠차에 해당 칸이 익는지를 적지
• bfs 밖의 반복문에서는 최소 일수를 구하고, 만약 최종적으로 안 익은 게 있을 경우 -1로 반환
• 0일차인데 1부터 시작했으므로 answer 반환할 때는 -1 해주기 (이 때 "저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력" 조건도 만족)

 

---

 

코드 구현 (Python 3)

 

from collections import deque

def BFS(m, n, box):
    queue = deque()

    for x in range(n):
        for y in range(m):
            if box[x][y] == 1:
                queue.append([x, y])
    
    while queue:
        x, y = queue.popleft()
        direction = [[-1, 0], [1, 0], [0, -1], [0, 1]]

        for dx, dy in direction:
            nx, ny = x + dx, y + dy

            # 벽이 아니고 방문한적 없는 경우
            if 0 <= x < n and 0 <= ny < m and box[nx][ny] == 0:
                box[nx][ny] = box[x][y] + 1
                queue.append([nx, ny])

    return box


def solution(m, n, box):
    answer = 0
    box = BFS(m,n,box)

    # 최소 일 수
    for x in range(n):
        for y in range(m):
            # 안익은거 있을 경우
            if box[x][y] == 0:
                return -1
        # 일수 갱신
        answer = max(answer, max(box[x]))
    return answer - 1


# m은 상자 가로 칸, n은 상자 세로 칸
m, n = map(int, input().split())
box = []

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

print(solution(m,n,box))

 

 

---

 

제출 결과