[백준] 토마토 7576 (Gold 5) - C++

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

 

문제 요약

• 2차원 격자에서 토마토가 익어간다.
• 1: 익은 토마토, 0: 안 익은 토마토, -1: 빈 칸
• 하루가 지나면 익은 토마토의 상하좌우 토마토가 익는다.
• 모든 토마토가 익기까지 걸리는 최소 일수를 구하라.
• 끝까지 익지 못하는 토마토가 있다면 -1 출력

문제를 보고 처음 든 생각들

문제를 딱 읽고 나서 정리한 생각은 이랬다.

1. 0이 고립되어 있으면 → 이건 무조건 fail
2. 입력 받을 때 1이 있는 위치는 전부 시작점이 될 수 있음
3. 하루 단위로 퍼져나가니까 DFS는 아니고 BFS
4. BFS를 다 돌고 나서 가장 깊은 depth가 정답일 듯?

 

❌ 처음에 시도한 방법 (실패)

내가 처음에 생각한 방식은 이거였다.

• 시작점(1)이 여러 개니까
• 각 시작점마다 BFS를 각각 실행
• depth를 기록한 격자를 하나 두고
• 여러 BFS 결과 중에서 가장 작은 depth만 남기자

말로 쓰면 그럴듯해 보이는데, 곧 문제가 보였다.

왜 안 되는가?

• BFS를 시작점 개수만큼 실행해야 함
• BFS 결과를 저장할 격자도 여러 개 필요
• 그걸 또 전부 비교해야 함

즉,

👉 BFS를 많이 돌리는 구조 자체가 이미 비효율적

실제로 이 방식으로 코드를 짜봤지만, 구조도 복잡해지고 성능도 별로였다.
(아래 코드는 이 방식으로 시도했다가 실패한 코드)

#include <bits/stdc++.h>

using namespace std;

int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};

vector<vector<int>> result_box;
vector<vector<int>> box;
void bfs(int i, int j);
int count_days();
int m, n;


int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>m>>n;
    box = vector<vector<int>> (n, vector<int>(m));//초기 입력값
    result_box= vector<vector<int>>(n, vector<int>(m)); //bfs depth 저장 box
    vector<pair<int,int>> starts;

    for(int i=0;i<n;i++){
        for(int j=0 ; j<m; j++){
            cin>>box[i][j];
            if(box[i][j]==1) starts.push_back({i,j}); // 초기 start들 저장해두기
        }
    }

    for(auto& tomato : starts){
        //각각의 start들을 차례대로 bfs를 한다.
        cout<<tomato.first<<'\n';
        bfs(tomato.first, tomato.second);
        
    }

    cout<<count_days(); //최종 날짜 

    return 0;
}

void bfs(int i, int j){
    queue<pair<int,int>> q;
    q.push({i,j});
    result_box[i][j]=1; //start를 1일로 함

    while(!q.empty()){
        auto[a,b] = q.front();
        q.pop();
        int old_depth=result_box[a][b];
        for(int k=0;k<4;k++){
            int ny= a+dy[k];
            int nx = b + dx[k];
            if(ny<0||ny>=n || nx<0 || nx>= m || box[ny][nx]==-1) continue; //경계검사
            int new_depth=result_box[ny][nx];
            if(new_depth>=1){
                result_box[ny][nx]= min(new_depth,old_depth+1);
            }
            if(new_depth==0) result_box[ny][nx] = old_depth+1;
            else result_box[ny][nx]= min(new_depth,old_depth+1);
        }
    }
}

int count_days(){
    int max=1;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(result_box[i][j]==0) return -1; //안 익은 토마토 발견
            if(result_box[i][j]>max){
                max=result_box[i][j]; // bfs 최종 맵에서 가장 큰 값 찾기
            }
        }
    }

    return max-1; //start를 1로 쳤으니 -1 해서 return
}

 

 

사고 전환 포인트

이 문제를 처음 이해하려고 했을 때는, 다음과 같 그림을 그리면서 생각했다.

• Day 0: 익어 있는 토마토들
• Day 1: 거기서 한 칸 떨어진 토마토들
• Day 2: 또 그 다음 칸들 ...

문제 해결 실패 후 다시 그림을 그리다 보니 BFS의 의미에 대해서 생각하게 되었다. 그림에서 여러 시작점들에서 근처를 단계별로 넓혀나가는 모양 자체가 BFS 같았다. 

BFS는 말 그대로 너비 우선 탐색이다. 그 의미는 다음과 같다.

• 큐에 들어간 순서대로 처리
• 같은 depth에 있는 노드들이 먼저 확장됨

그렇다면:

• 시작점이 여러 개라면?
• 처음부터 큐에 시작점이 다 있다면 단계적으로 확장하면 되지 않을까?

🔑 다중 시작점 BFS

이 아이디어를 떠오른 후 수도 코드를 작성하며 생각을 정리해보았다. 

1. 입력을 받으면서
   • 1인 좌표를 전부 큐에 넣기
   • 이 좌표들의 depth를 1로 설정
2. 큐가 빌 때까지 BFS
   • 상하좌우 확인
   • 아직 방문 안 한 0만 방문
   • depth = 이전 depth + 1
3. BFS 종료 후 검사
   • 0이 남아 있으면 -1
   • 아니면 depth의 최댓값 - 1

겹치는 경우는?

서로 다른 시작점에서 퍼진 BFS가 중간에 만나는 경우가 생길 수 있다.
근데 이건 신경 쓸 필요가 없다.

• BFS 특성상 더 가까운 쪽이 먼저 방문 처리됨
• 나중에 도착한 경로는 이미 visited라서 자연스럽게 무시됨

추가 비교 로직이 필요 없다.

---

최종 코드 (C++)

#include <bits/stdc++.h>

using namespace std;

int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};

vector<vector<int>> result_box;
vector<vector<int>> box;
void bfs(queue<pair<int,int>> q);
int count_days();
int m, n;


int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>m>>n;
    box = vector<vector<int>> (n, vector<int>(m));//초기 입력값
    result_box= vector<vector<int>>(n, vector<int>(m)); //bfs depth 저장 box
    queue<pair<int,int>> starts;

    for(int i=0;i<n;i++){
        for(int j=0 ; j<m; j++){
            cin>>box[i][j];
            if(box[i][j]==1) starts.push({i,j}); // 초기 start들 저장해두기
        }
    }

    bfs(starts);

    cout<<count_days(); //최종 날짜 

    return 0;
}

void bfs(queue<pair<int,int>> starts){
    queue<pair<int,int>> q;
    while(!starts.empty()){
        auto[a,b]=starts.front();
        starts.pop();
        q.push({a,b});
        result_box[a][b]=1; //start를 1일로 함
    }

    while(!q.empty()){
        auto[a,b] = q.front();
        q.pop();
        int old_depth=result_box[a][b];
        for(int k=0;k<4;k++){
            int ny= a+dy[k];
            int nx = b + dx[k];
            if(ny<0||ny>=n || nx<0 || nx>= m || box[ny][nx]==-1) continue; //경계검사
            if(result_box[ny][nx]>=1) continue; //이미 visited은 pass
            q.push({ny,nx});
            result_box[ny][nx]=old_depth+1; //depth 추가
        }
    }
}

int count_days(){
    int max=1;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(result_box[i][j]==0 && box[i][j]==0) return -1; //고립된 안 익은 토마토 발견
            if(result_box[i][j]>max){
                max=result_box[i][j]; // bfs 최종 맵에서 가장 큰 값 찾기
            }
        }
    }

    return max-1; //start를 1로 쳤으니 -1 해서 return
}

 

시간 복잡도

입력 처리, BFS 탐색, 결과 검사 모두 O(n *m) 시간복잡도이다.