문제

문제링크

각 원소가 하나씩 전파되는 문제되어 총 얼마나 걸리는지 구하는 문제다.
python으로 코딩했을때는 큐를 쓸때 리스트를 타입으로 넣어줬었다.
근데 c++은 pair을 써서 first,second 필드로 사용한다.

근데 이 문제에서 bfs를 쓰는데 트리의 깊이를 체크해줬어야했다.
한번 전파(트리 깊이)할때마다 한칸씩 움직이는데
최종 얼마나 전파되었는지 체크해야했다.

기존 bfs 문제에서는 단순히 queue가 빌때까지 계속 돌면되었는데
트리의 깊이를 생각해줘야하니 y,x,depth 이렇게 3개를 고려해야했다.

vector

그래서 queue 타입으로 pair가 아닌 vector를 사용했다.
대충 검색해본 결과 vecotr는 동적으로 원소 추가가 가능한고 배열처럼 인덱스로 접근이 가능했다. 근데 저장할때 순서대로 저장하는게 아니여서 list처럼 처음부터 찾아야하나보다. 그래서 vector가 너무 커지면 접근 시간이 오래걸릴듯하다.

big o

bfs 자체만 생각하면 그래프의 크기(mn) 에 상하좌우(4) 해서 mn*4의 빅오를 생각할수있다.

근데 마지막에 빈칸없이 탐색을 성공했는지 체크해야했다. 보통 전체탐색하면 탐색할때마다 체크를해서 true일때만 탐색해서 check의 시간 복잡도가 n^2면 bfs도 n^3이 된다.

다행히 이번에는 check를 마지막에 한번만해서 n^2로 해도 괜찮았지만
그래도 다른 문제를 풀때 이러한 점을 생각하기 위해 vacant라는 빈칸수를 체크해 상수시간으로 check하도록 했다.

code

/**
 * 백준 7576
 * BFS 문제
 * 토마토가 전파되는데 그래프를 채우기 위해 걸리는 일수
 * 동서남북으로 이동하는 BFS 문제
*/
#include <bits/stdc++.h>
using namespace std;

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

int m,n;
int graph[1001][1001];
vector<pair<int,int>> starts;
int vacant = 0; // 빈칸
int ansCnt=0;

int bfs(){
    queue<vector<int>> que;
    for(pair<int,int> start:starts){
        que.push({start.first,start.second,0});
    }

    int ret=0;

    while(!que.empty()){
        vector<int> now = que.front();
        que.pop();

        int ny=now[0];
        int nx=now[1];
        // 상하좌우
        for(int i=0;i<4;i++){
            int my=dy[i]+ny;
            int mx=dx[i]+nx;
            int cnt=now[2];

            if (my<0 or my>=m or mx<0 or mx>=n){
                continue;
            }

            else if(graph[my][mx] == 0){
                graph[my][mx]=1;
                vacant--;
                ret=(cnt+1>ret)?cnt+1:ret; // 최대 움직인수
                que.push({my,mx,cnt+1});
            }
        }
    }
    // 완료한 상태
    if(vacant == 0){
        return ret;
    }
    else{
        return -1;
    }
}

int main(){
    cin >>n>>m;

    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            scanf("%d",&graph[i][j]);
            // 시작점
            if(graph[i][j]==1){
                starts.push_back({i,j});
            }
            else if(graph[i][j]==0){
                vacant++;
            }
        }
    }

    cout << bfs();
}