백준 7576 토마토

문제

토마토

토마토가 다 익기까지 걸리는 날짜를 구하자

난이도 : Gold5

---

풀이

1. 가장 마지막 행에 있는 2의 위치를 찾는다.
2. 1을 타고 거꾸로 올라가며 첫 째 행에서 1을 만나면 종료하고 열의 위치를 출력한다.

---

코드

import sys
from collections import deque

n, m = list(map(int, sys.stdin.readline().split()))
data = [list(map(int, sys.stdin.readline().split())) for _ in range(m)]
direction = [(0, 1), (1, 0), (-1, 0), (0, -1)]

def check_initial(d):
    if 0 not in [j for i in d for j in i]:
        return 0  # 상자에 안 익은 토마토가 없음 (0 출력)
    elif 1 not in [j for i in d for j in i]:
        return 1  # 익은 토마토가 상자에 없음 (-1 출력)
    else:
        return 2  # infect 함수 실행 조건

def check(d):  # 익은 토마토 위치 반환
    temp_list = []
    for i in range(m):
        for j in range(n):
            if d[i][j] == 1:
                temp_list.append((i, j))
        
    return temp_list
    
def infect(tup_list):
    day = 0
    q = deque()
    for t in tup_list:
        q.append(t)
    temp = q[-1]  # day를 +1 하게 될 조건을 위한 변수
    
    while True:
        tup = q.popleft()       
        for i in range(4):  # 네 방향을 모두 돌면서 전파
            nc, nr = tup[0], tup[1]
            nc = nc + direction[i][0]
            nr = nr + direction[i][1]

            if 0 <= nc < m and 0 <= nr < n:
                if data[nc][nr] == 0:
                    data[nc][nr] = 1
                    q.append((nc, nr))
        
        if not q:  # 더 이상 접근할 원소가 없으면 break
            break   
        
        if tup == temp:  # in / not in은 최대한 사용 지양할 것
            temp = q[-1]  # 큐의 맨 마지막 원소가 pop될 때 하루씩 추가해 주고, 해당 시점 큐의 마지막 원소를 temp로 재할당
            day += 1
        
    if 0 in [j for i in data for j in i]:  # bfs가 종료됐음에도 0이 남아있음 (토마토를 다 익게 할 수 없는 상황)
        day = -1
        return day
    else:
        return day

if check_initial(data) == 0:
    print(0)
elif check_initial(data) == 1:
    print(-1)
else:
    point = check(data)
    print(infect(point))

        

---

결과

첫 그래프 탐색 문제라 너무 어려웠다. 솔브하는데만 3일이 넘게 걸렸다..
비교 연산으로 in을 사용했다가, 등호 연산자를 사용하니 시간 초과를 면했다.