7569. [Python]토마토

1. 문제

 

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

7569번: 토마토

 

2. 접근 방법

 

• 시간 제한: 1초
• 메모리 제한: 256MB
• 그래프 탐색

 

3. 파이썬 코드

 

import sys
from collections import deque

input = sys.stdin.readline

N, M, H = map(int,input().split())

tomato = [ list(map(int,input().split())) for _ in range(M*H) ]

direction = [(-1,0), (0,1), (1,0), (0,-1)]

tomato_list = deque([])
# 일수 체크
day = 0
# 0의 개수 체크
zero_cnt = 0
# 익은 토마토 위치와 익지않은 토마토 개수 체크
for i in range(M*H):
    for j in range(N):
        if tomato[i][j] == 1:
            tomato_list.append((i,j))
        elif tomato[i][j] == 0:
            zero_cnt += 1
# 익지 않은 토마토가 없는 경우 바로 종료
if zero_cnt == 0:
    print(0)
    exit()
# 몇번 반복할지 몰라서 계속 반복
while True:
    # 임시 저장할 리스트
    check_list = deque([])
    # 토마토 위치가 없을때까지 반복
    while tomato_list:
        check = tomato_list.popleft()
        # 고른 토마토 위치가 몇번째 높이인지 체크
        range_check = check[0] // M
        # 방향배열 탐색
        for k in range(4):
            ny = direction[k][0] + check[0]
            nx = direction[k][1] + check[1]
            # 범위 내에 존재할 경우
            if (0 <= ny < M*H) and (0 <= nx < N):
                # 현재 고른 위치 내에서만 탐색
                if range_check * M <= ny < (range_check + 1) * M:
                    # 익지않은 토마토인 경우 토마토 익히고 개수 -1 후 위치 추가
                    if tomato[ny][nx] == 0:
                        tomato[ny][nx] = 1
                        zero_cnt -= 1
                        check_list.append((ny,nx))
        # 현재 뽑은 위치에서 위아래 층 도 익힘
        nh = check[0] + M
        nmh = check[0] - M

        if 0 <= nh < M*H:
            if tomato[nh][check[1]] == 0:
                tomato[nh][check[1]] = 1
                zero_cnt -= 1
                check_list.append((nh,check[1]))
    
        if 0 <= nmh < M*H:
            if tomato[nmh][check[1]] == 0:
                tomato[nmh][check[1]] = 1
                zero_cnt -= 1
                check_list.append((nmh,check[1]))
    # 더이상 토마토를 체크할 수 없을 때 반복문 탈출
    if not check_list and not tomato_list:
        break
    # 외의 경우 임시 저장한 리스트를 토마토 리스트에 추가 후 하루가 지남
    else:
        tomato_list = check_list
        day += 1
# 만약 반복문이 끝난 후 토마토가 익지않은 것이 있을 경우 -1 출력
if zero_cnt == 0:
    print(day)
else:
    print(-1)

 

4. 문제를 풀고난 후 생각

 

• 기존의 토마토와 비슷한 문제지만 층이 나뉘어 진 다른 문제이다.
• 2차원 배열 형태로 풀었고, 현재 위치가 몇층에 있는지를 확인한 후 그 층내에서 방향배열을 탐색하는 식으로 진행했다.
• 이후 층 위아래 칸에 토마토가 있어도 익어갈 수 있도록 BFS를 돌려주었고, BFS 외부에 while 문을 처리하여 몇번 시행할지 모르는 반복문을 돌려줬다.
• 리스트 두개가 비어있고, 익지 않은 토마토가 있는 경우 -1을 외의 경우 day를 출력해주는 방식으로 풀었다.

 

5. 문제를 푸는데 도움이 되는 지식

 

• 그래프 탐색
• 그래프 이론