[문제 풀이] 백준 7576

해결 과정

그래프 상하좌우 탐색 방법은 이전에 알고 있어서 적용 가능했다. while 문으로 다 처리했는데, 답은 잘 나오지만 시간초과가 발생했다. 문제 유형에 너비우선탐색(BFS)가 있길래, Queue를 떠올리며 시간 초과를 어떻게 없앨지 생각하다가, 이전 풀이에서는 이미 탐색한 것도 재탐색하는 비효율이 있음을 알게 됐다. 다음을 추가해서 시간초과 문제를 해결했다.

• ripedTomatosCount를 추가해서 전체 처리 개수 세도록 했고,
• while 문 내에서 for 문 돌릴 때, 이미 센 것에 대해선 처리하지 않도록 처리함. (ripedTomatos = newRipedTomatos 재할당)

나의 풀이

def solution(m, n):
    answer = 0
    dx = [0, 1, 0, -1]
    dy = [-1, 0, 1, 0]
    
    # 익은 토마토 찾기
    ripedTomatos = []
    rottenTomatosCount = 0
    
    for i in range(n):
        for j in range(m):
            if box[i][j] == 1:
                ripedTomatos.append((i, j))
            elif box[i][j] == -1:
                rottenTomatosCount += 1

    ripedTomatosCount = len(ripedTomatos)
    
    # 이미 다 익은 상태라면
    if ripedTomatosCount + rottenTomatosCount == m*n:
        return 0

    # 날짜 세기
    while True:
        # 처리 하기
        newRipedTomatos = []
        for tomoto in ripedTomatos:
            for x, y in zip(dx, dy):
                xx = tomoto[0] + x
                yy = tomoto[1] + y
                if xx >= 0 and yy >= 0 and xx < n and yy < m and box[xx][yy] == 0:
                    box[xx][yy] = 1
                    newRipedTomatos.append((xx, yy))
                    ripedTomatosCount += 1
        answer += 1

        # 익지 않는 경우가 존재하면
        if len(newRipedTomatos) == 0:
            return -1
        
        # 이미 다 익은 상태라면
        if ripedTomatosCount + rottenTomatosCount == m*n:
            return answer
        
        ripedTomatos = newRipedTomatos

M, N = map(int, input().split())
box = [list(map(int, input().split())) for _ in range(N)]

print(solution(M, N))