7576번. 토마토

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

 

 

BFS로 푸는 문제이다.

처음 접근방법은 처음부터 익은 토마토 리스트를 하나 만든 후에, 그 중 하나가 주변을 익힐 수 있을 만큼 모두 익히게 하고,

그 다음 처음부터 익은 토마토가 또 주변을 익힐 수 있게 하되, 더 이른 날짜에 익을 수 있으면 날짜를 교체하도록 했다.

그렇게 하니 보기 좋게 시간초과가 생겼고, 날짜를 그렇게 변경해나가는 것은 BFS가 아니라는 질문 글을 발견했다.

도착한 순간 최단 경로가 확정되어야 한다는 것이다. 즉, 재방문 하는 일이 없어야 한다.

잘못 생각했던 점은 한 토마토의 주변을 일단 모두 익게 하려고 했다는 점이다.

익은 각각의 토마토들의 상하좌우를 각각 한번씩만 익힌 후 그것을 모두 큐에 넣고, 날짜를 하나 증가시킨 후 또다시 각각의 상하좌우를 큐에 넣고...하는 식으로 하면 된다.

소스코드 상으로는 처음부터 익은 토마토를 큐의 초기값으로 잡으면 된다.

 

채점한 코드 중에 중요한 함수만 가지고 왔다.

def start_ripe_tomato():
    queue = collections.deque()
    queue.extend(initiate_tomato())  # 처음에 1인 토마토 리스트

    while queue:
        r, c = queue.popleft()
        for nR, nC in [[r + 1, c], [r - 1, c], [r, c + 1], [r, c - 1]]:  # 상하좌우
            if 0 <= nR < n and 0 <= nC < m:
                if box[nR][nC] == 0:  # 아직 안 익었다면
                    queue.append([nR, nC])  # 큐에 추가. 큐에는 방금 익은 리스트가 들어감
                    box[nR][nC] = 1  #  익음 체크
                    days[nR][nC] = days[r][c] + 1

2) 큐를 사용하기 위해서 collections의 덱을 사용한다.

3) initiate_tomato()는 처음에 주어진 입력에서 1인 토마토들을 모두 리스트에 저장해 반환하는 함수이다. queue에는 방금 익은 토마토들이 들어갈 리스트인데, 초기값으로는 처음부터 익어 있었던 (1이었던) 토마토들을 방금 익은 것이라고 가정하고 넣는다.

5) 방금 익은 토마토(queue)들이 없을 때까지 진행한다. 방금 익은 토마토가 없다면 더이상 진행이 불가능할 것이기 때문이다.

6~8) 각각의 토마토들의 상하좌우를 가져와서 out of index 체크를 한다.

9) 토마토가 아직 익지 않은 상태라면, 그것을 익히고 (11번줄), 방금 익은 토마토 리스트에 추가한다. (10번줄)

12) days는 각각의 토마토가 익을 때까지 걸리는 일수를 저장한 이차원 리스트인데, 부모 토마토가 익은 날짜+1이 된다.

 

다시 와서 생각해보면 BFS에서 크게 벗어나지 않은 문제인데, 미로찾기처럼 생각해서 헤맨 문제같다.