[코딩테스트 C++] 토마토

오늘의 문제

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

토마토

참고한 풀이

#include <iostream>
#include <string>
#include <vector>
#include <queue>
using namespace std;
 
const int MAX = 1000;
vector<vector<int>> box(MAX, vector<int>(MAX, 0));
bool visit[MAX][MAX] = {false, };
int n, m;
int di[] = {1, -1, 0, 0};
int dj[] = {0, 0, 1, -1};
queue<pair<pair<int, int>, int>> q;
int cnt;
// 토마토
void solution(){
    while(!q.empty()){
        int row = q.front().first.first;
        int col = q.front().first.second;
        cnt = q.front().second;
        q.pop();
        for(int i=0;i<4;i++){
            int R = row + di[i];
            int C = col + dj[i];
            if(R>=n || R<0 || C>=m || C<0)
                continue;
            if(visit[R][C] == false && box[R][C] == 0){
                visit[R][C] = true;
                q.push(make_pair(make_pair(R, C), cnt +1));
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin>>m >>n;
    vector<vector<int>> pair;
    for(int j=0;j<n;j++){
        for(int i = 0;i<m;i++){
            cin>>box[j][i];
            if(box[j][i] == 1){
                q.push(make_pair(make_pair(j, i), 0));
                visit[j][i] = true;
            }
        }
    }
    solution();
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(!visit[i][j] && box[i][j] == 0){
                cout<<-1<<endl;
                return 0;
            }
        }
    }
    cout<<cnt<<endl;
    return 0;
}

배울 점

• BFS활용법을 또 하나 배웠다. 시작되어야하는 점을 알고 있으면, 모든 지점에서부터의 가장 짧은 depth를 알 수 있다.
• 그래프문제를 풀 때 아주 잘 쓸 수 있을것 같다.