문제

Code

#include <iostream>
#include <queue>
#include <utility>

using namespace std;
int board[1002][1002];
int dist[1002][1002];
#define X first
#define Y second
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int N, M, max_day;

bool check(){
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++)
        {
            if(board[i][j] == 0) return false;
        }
    return true;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    queue<pair<int,int>> Q;

    cin >> M >> N; // M:열(y) / N:행(x)
    for(int i=0;i<N;i++)
    {
        fill(dist[i], dist[i]+M, -1);
        for(int j=0;j<M;j++)
        {
            cin >> board[i][j];
            if(board[i][j] == 1)
            {
                Q.push({i,j});
                dist[i][j] = 0;
            }
        }
    }

    while(!Q.empty())
    {
        auto cur = Q.front(); Q.pop();
        for(int dir=0;dir<4;dir++)
        {
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];
            if(nx<0 || nx>=N || ny<0 || ny>=M) continue;
            if(board[nx][ny] != 0 || dist[nx][ny] != -1) continue;
            dist[nx][ny] = dist[cur.X][cur.Y]+1;
            Q.push({nx,ny});
            max_day = max(max_day,dist[nx][ny]);
            board[nx][ny] = 1;
        }
    }
    if(check())
        cout << max_day;
    else
        cout << -1;
}

• 정점 여러개에서 같이 BFS 시작하기 위해
     --> board[i][j]가 1일 때 바로 Q.push({i,j});
            동시에 dist[i][j]도 0으로 만들어준다.
• max 함수 이용해서 크기비교

    max_day = max(max_day,dist[nx][ny]);

• 시간초과 나기 쉬운문제라서 유의해야함
• 1년전 코드보다 똑똑해진걸보니 멍청해지지는 않은듯;