백준 7576 토마토 파이썬 풀이, 시간초과 해결

난이도 : 골드5
풀이일 : 04145
https://www.acmicpc.net/problem/7576

7576번: 토마토

---

링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐

---

1차 시도 오답

# 익은 토마토 발견 시, 리스트에 추가
# 리스트를 인자로 하는 함수에서 토마토 인근 4방향 탐색
# 익지 않은 토마토가 있다면, -1 출력

import sys

# 익은 토마토 찾기 함수
def tomato(arr):
    red = []
    for a in range(n):
        for b in range(m):
            if arr[a][b] == 1:
                red.append(a)
                red.append(b)
    change(arr, red)

    day = 0
    for a in range(n):
        for b in range(m):
            if arr[a][b] == 0:
                return print(-1)
            if arr[a][b] > day:
                day = arr[a][b]

    return print(day-1)

# 토마토 익히기
def change(arr, q):
    queue = q
    while queue:
        i = queue.pop(0)
        j = queue.pop(0)
        di, dj = [-1, 1, 0, 0], [0, 0, -1, 1]
        for k in range(4):
            ni, nj = i + di[k], j + dj[k]
            if 0 <= ni < n and 0 <= nj < m and arr[ni][nj] == 0:
                arr[ni][nj] = arr[i][j] + 1
                queue.append(ni)
                queue.append(nj)
    return

m, n = list(map(int, sys.stdin.readline().split()))
box = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

tomato(box)

코드 구성
1. 2차원 배열을 입력 받고 익은 토마토 찾는 함수 tomato 실행
2. tomato 함수는 익은 토마토 좌표를 리스트에 담아 날짜 확인 함수 change에 전달
3. change 함수에서는 토마토 숙성 과정 진행 후 리턴
4. tomato 함수로 돌아와 2차원 배열 순회, 최대날짜 -1 (첫 토마토가 1부터 시작) 출력 반환
5. 안익은 토마토가 있다면 최대날짜 대신 -1 출력 반환
 
틀린 이유
1. 시간 초과 -> pop 연산 때문으로 추측

---

최종 정답

# 익은 토마토 발견 시, 리스트에 추가
# 리스트를 인자로 하는 함수에서 토마토 인근 4방향 탐색
# 익지 않은 토마토가 있다면, -1 출력

import sys

# 익은 토마토 찾기 함수
def tomato(arr):
    red = []
    for a in range(n):
        for b in range(m):
            if arr[a][b] == 1:
                red.append(a)
                red.append(b)
    change(arr, red)    # 토마토 숙성

    # 전체 숙성 여부 및 기간 판별
    day = 0
    for a in range(n):
        for b in range(m):
            if arr[a][b] == 0:
                return print(-1)
            if arr[a][b] > day:
                day = arr[a][b]

    return print(day-1)

# 토마토 숙성 함수 시간 인덱스 활용으로 시간 초과 해결
def change(arr, q):
    queue = q
    x = 0
    while x < len(queue):
        i = queue[x]
        x += 1
        j = queue[x]
        x += 1
        di, dj = [-1, 1, 0, 0], [0, 0, -1, 1]
        for k in range(4):
            ni, nj = i + di[k], j + dj[k]
            if 0 <= ni < n and 0 <= nj < m and arr[ni][nj] == 0:
                arr[ni][nj] = arr[i][j] + 1
                queue.append(ni)
                queue.append(nj)
    return

m, n = list(map(int, sys.stdin.readline().split()))
box = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

tomato(box)

코드 변화
 
1. pop 대신 포인터 x로 인덱스를 이용 -> pop 연산 속도 문제 해결

---

느낀점
처음 풀었을 당시에는 포인터 개념을 몰라서 훨씬 헤맸던 기억이 난다.
익숙한 유형의 문제만 모아 풀며 기분좋아하지 말고 새로운 개념 학습이 필요한 부분을 찾아 공부하면 더 다양한 방식으로 문제 풀이를 시도해볼 수 있을 것 같다.
맨날 어려워서 대충 넘겨버리는 주제들을 이제부터라도 개념을 공부하고 문제 풀이 시도해봐야지