백준 7576번, 토마토

백준 7576번 c++ 문제풀이

문제:

백준 7576

풀이:

1. 토마토가 심긴 땅에 대한 정보를 n은 세로, m은 가로길이로 이중 벡터에 저장한다.
2. 저장된 정보를 바탕으로 너비우선탐색을 실행
3. 저장된 수가 1인 벡터부터 시작한다.
4. 저장된 수가 1인 벡터부터 (x+1,y), (x-1,y), (x,y+1), (x, y-1)방향을 연결되어 있는 노드로 본다.
5. 각 노드로 이동하며 너비우선탐색을 실행한다. 이동 시 이전 벡터의 저장된 숫자의 +1로 현재 벡터의 값을 업데이트 해준다.
6. 다시 저장된 벡터 값 중 가장 큰 값 - 1(1부터 시작했기에)을 출력한다. 만약 저장된 값 중 0이 있다면,
   토마토가 모두 익지 않은 상황이므로 -1을 출력한다.

코드:

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

using namespace std;

void dfs(vector<vector<int>> v, int m, int n){
    queue<pair<int, int>> q; //dfs를 위한 큐 생성, x,y좌표.
    vector<vector<bool>> visited(n, vector<bool>(m, false));//해당 좌표를 들렀는지 확인하기 위함

    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(v[i][j] == 1){//값이 1부터 시작
                q.push({i, j});//처음 시작하는 좌표들을 큐에 푸쉬
                visited[i][j] = true; //방문했슴
            }
        }
    }

    while(!q.empty()){//큐가 비워지기 전까지 반복
        int x1, y1;

        y1 = q.front().first;
        x1 = q.front().second;

        q.pop();
        //밑에는 모든 방향확인하기 조건
        if(x1+1 < m){
            if(v[y1][x1+1] == 0 && visited[y1][x1+1] == false){
                q.push({y1, x1+1});
                visited[y1][x1+1] = true;
                v[y1][x1+1] = v[y1][x1]+1;
            }
        }
        if(x1-1 >= 0){
            if(v[y1][x1-1] == 0 && visited[y1][x1-1] == false){
                q.push({y1,x1-1});
                visited[y1][x1-1] = true;
                v[y1][x1-1] = v[y1][x1]+1;
            }
        }
        if(y1+1 < n){
            if(v[y1+1][x1] == 0 && visited[y1+1][x1] == false){
                q.push({y1+1, x1});
                visited[y1+1][x1] = true;
                v[y1+1][x1] = v[y1][x1]+1;
            }
        }
        if(y1-1 >= 0){
            if(v[y1-1][x1] == 0 && visited[y1-1][x1] == false){
                q.push({y1-1, x1});
                visited[y1-1][x1] = true;
                v[y1-1][x1] = v[y1][x1]+1;
            }
        }
    }

    int max = 0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(v[i][j] > max){
                max = v[i][j];
            }
            if(v[i][j] == 0){ //만약 bfs로 갈수 없는 곳이 있어 0인곳이 있다면, 토마토가 다 변할 수 없기에 -1출력
                cout << -1;
                return;
            }
        }
    }

    cout << max -1;
}

int main() {

    int m,n;

    cin >> m >> n; //가로 세로

    vector<vector<int>> v;

    for(int i=0;i<n;i++){
        vector<int> v1;
        for(int j=0;j<m;j++){
            int t;
            cin >> t;
            v1.push_back(t);
        }
        v.push_back(v1);
    }

    dfs(v,m,n);

    return 0;
}

감사합니다.