[C++] BOJ 7576 / BFS 응용(시작점이 여러 개)

문제 분석

BFS 기초 문제를 풀다보면 만나는 문제이다. 문제의 조건에 토마토의 개수가 1개로 고정된다는 말이 없으므로, 토마토의 개수가 여러 개 일 수 있으며, 이말은 즉 BFS를 돌릴 때의 시작점이 여러개라는 뜻이다.

 

해결 방법

시작점이 여러 개인 BFS의 경우, 모든 시작점을 큐에 넣고 BFS를 돌면 자연스럽게 거리가 구해진다.

 

코드

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

using namespace std;
#define X first
#define Y second
int board[1001][1001];
bool vis[1001][1001];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,-1,0,1};

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    queue<pair<int,int>> q;
    int n, m, k;
    int max=0;
    cin >> m >> n;
    for(int i=0;i<n;i++) {
        for(int j=0;j<m;j++) {
            cin >> k;
            board[i][j] = k;
            if(k == 1) {	// 시작위치 전부 큐에 넣기
                q.push({i,j});
                vis[i][j] = 1;
            }
        }
    }
    while(!q.empty()) {
        pair<int,int> 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(vis[nx][ny] || board[nx][ny] != 0) continue;
            vis[nx][ny] = 1;
            q.push({nx,ny});
            board[nx][ny] = board[cur.X][cur.Y] + 1;
        }
    }
    for(int i=0;i<n;i++) {
        for(int j=0;j<m;j++) {
            if(board[i][j] == 0) {
                cout << -1;
                return 0;
            }
            max = board[i][j] > max ? board[i][j] : max;
        }
    }
    cout << max - 1;
    return 0;
}