토마토(백준 7576)

(출처) https://www.acmicpc.net/problem/7576

📖 개요

익은 토마토(노드)에 인접해져 있는 토마토는 다음턴에 익은 토마토로 변한다. 턴을 반복해 토마토가 모두 익게되기까지 총 몇턴이 소모 되는지를 파악해 출력하는 문제.

매턴 익은 토마토 노드를 방문해 다음턴으로 방문할 노드를 기록하면 되기때문에 BFS 알고리즘을 이용하면 문제를 해결할 수 있을 것 같았다.

입력으로 주어지는 2차원 배열의 크기, 즉 노드의 총 개수는 백만개이며, 각 노드는 상하좌우 총 4개씩의 간선을 가지고 있으므로 BFS 탐색을 통한 총 반복수행 횟수는 약 5백만 정도로 추정됐다 // BFS의 시간복잡도 : O(V+E)

따라서 시간제한 조건은 전혀 신경쓰지 않아도 될 것 같았다.

✨ BFS 탐색

문제에서 결과값으로 요구하는 것은 총 소요일이 얼마인지에 대한 그 계산값 이다. 즉 턴을 계산해야한다는 조건이 걸려있으므로, 기본적으로 BFS로 문제를 해결하되 다음으로 탐색해야할 노드를 Queue에 추가할 때 약간의 처리를 해줘야할 필요성을 느꼈다.

정확하게는 Queue에 방문예정 노드를 추가할때, 오늘 방문할 노드와 내일 방문할 노드를 명확하게 구분할 필요가 있었다.

턴에 대한 경과(오늘과 내일)를 하나의 Queue에서 구분짓기에는 조금 번잡해보였으므로 나는 2개의 큐를 운용해서 BFS를 돌리는 방식으로 구현을 해보기로 하였다.

즉 Today Queue와 Tomorrow Queue를 동시에 운용하는 것이다. 자세한 방식에 대해 설명해보자면, Today Queue에 등록된 노드들을 하나씩 방문하면서 다음 방문해야하는 노드들은 Tomorrow Queue에 추가한다. Today Queue에 등록된 노드들을 전부 방문해서 Today Queue가 완벽하게 비게되면 한 턴을 모두 소모한 것이다. 따라서 소모일을 +1 해주고 Tomorrow Queue에 있는 노드들을 Today Queue로 전부 옮긴 뒤 다시 다음턴을 시작한다. 이 후 양쪽 Queue가 전부 비게되면 더이상 방문해야할 노드가 없다는 것이므로 최종적으로 소모일을 Return 해주면 된다. (물론 Return을 하기 전에, 익을 수 없는 토마토가 존재했는지 맵을 스캔해보고 예외까지 처리해준다)

🎨 코드

#include <vector>
#include <iostream>
#include <queue>

using namespace std;

int main() {
    int M,N;
    cin >> M >> N;
    vector<vector<int>> box(N,vector<int>(M,0));
    queue<pair<int,int>> today, tommorw;
    int result = 0;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            cin >> box[i][j];
            //만약 현재 입력받은 값이 익은 토마토(value = 1)인 경우 today Queue에 등록
            if(box[i][j] == 1) today.push(pair<int,int>(i,j));
        }
    }
    int direction[4][2] = {{-1,0}, {1,0}, {0,-1}, {0,1}}; //상하좌우
    //BFS >> 더이상 방문해야할 노드가 없을 때까지 탐색을 수행
    while(!today.empty() || !tommorw.empty()) {
        //더이상 오늘 방문할 노드가 존재하지 않을 경우 다음날로 진행
        if(today.empty()) {
            today = tommorw;
            tommorw = queue<pair<int,int>>();
            result++;
            continue;
        }
        //해당 라인부터는 Today Queue의 노드들을 방문하는 로직
        pair<int,int> curr_tomato = today.front();
        today.pop();
        for(int i = 0; i < 4; i++) {
            int nextY= curr_tomato.first + direction[i][0];
            int nextX = curr_tomato.second + direction[i][1];
            if(nextY < 0 || nextY >= N || nextX < 0 || nextX >= M) continue; //맵을 벗어나는 경우
            if(box[nextY][nextX] == -1) continue; //해당 위치에 토마토가 존재하지 않는 경우(벽이라고 생각)
            if(box[nextY][nextX] == 1) continue; //이미 익은 토마토인 경우
            //발견한 노드가 위 3가지 if 조건에 모두 해당하지 않는 경우는 익지 않은 토마토인 경우뿐이므로 tommrow Queue에 등록하고 map도 변경해준다
            box[nextY][nextX] = 1;
            tommorw.push(pair<int,int>(nextY,nextX));
        }
    }
    //모든 턴을 수행한 후에 맵에 익지않은 토마토가 존재하는 지 검사. 만약 존재한다면 -1를 return
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            if(box[i][j] == 0) {
                result = -1;
                break;
            }
        }
    }

    cout << result;
    return 0;
}