백준 : 7576번 토마토(C++14)_BFS

핵심

출발점이 여러개가 될 수 있다면 BFS 시작전 출발점을 모두 큐에 넣어주고 시작하면 된다.

풀이

// 2020-05-22 wsshin

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

int Solution(int SizeY, int SizeX, vector<vector<int>> vecBoard);

int main()
{
    int SizeY = 0;
    int SizeX = 0;

    cin >> SizeX >> SizeY;

    vector<vector<int>> vecBoard;


    for (int i = 0; i < SizeY; i++)
    {
        vector<int> nTemp;
        for (int j = 0; j < SizeX; j++)
        {
            int nInput = 0;
            cin >> nInput;
            nTemp.push_back(nInput);
        }
        vecBoard.push_back(nTemp);
    }


    int Result = Solution(SizeY, SizeX, vecBoard);

    cout << Result;

    return 0;
}

int Solution(int SizeY, int SizeX, vector<vector<int>> vecBoard)
{
    // 시계방향 상우하좌
    int dY[4] = { -1, 0, 1, 0 };
    int dX[4] = { 0, 1, 0, -1 };

    vector<vector<int>> vecVist(SizeY, vector<int>(SizeX, 0));
    vector<vector<int>> vecDay(SizeY, vector<int>(SizeX, 0));

    int nRipeTomatoCnt = 0;
    int nDayCnt = 0;
    int nNull = 0;
    bool IsAllRipe = true;


    vector<pair<int, int>> vecStartTomatoPos;

    queue<pair<int, int>> queue;

    //1. 최초 익은 토마토의 위치 찾기 및 스타트 정보 큐에 등록
    for (int Y = 0; Y < SizeY; Y++)
    {
        for (int X = 0; X < SizeX; X++)
        {
            if (vecBoard[Y][X] == 1)
            {
                queue.push(make_pair(Y, X));
                vecVist[Y][X] = 1;
                vecDay[Y][X] = 0;
                nRipeTomatoCnt++;
            }
            else if (vecBoard[Y][X] == 0)
            {
                IsAllRipe = false;
            }
            else if (vecBoard[Y][X] == -1)
            {
                nNull++;
            }
        }
    }

    // 이미 다 익어있다면 그냥 0반환
    if (IsAllRipe == true) return 0;


    //2. 실제 BFS 실행
    while (!queue.empty())
    {
        int CurY = queue.front().first;
        int CurX = queue.front().second;
        queue.pop();

        // 사방이 막혀있는지 확인
        int nBlock = 0;

        for (int i = 0; i < 4; i++)
        {
            int PushY = dY[i] + CurY;
            int PushX = dX[i] + CurX;

            if (PushY < 0 || PushY >= SizeY) continue;
            if (PushX < 0 || PushX >= SizeX) continue;
            if (vecBoard[PushY][PushX] == -1) continue;
            if (vecVist[PushY][PushX] == 1) continue;

            queue.push(make_pair(PushY, PushX));
            vecVist[PushY][PushX] = 1;
            vecDay[PushY][PushX] = vecDay[CurY][CurX] + 1;
            nRipeTomatoCnt++;
            nBlock = 0;

            if (nDayCnt < vecDay[PushY][PushX])
            {
                nDayCnt = vecDay[PushY][PushX];
            }
        }
    }

    if (nRipeTomatoCnt < ((SizeY * SizeX) - nNull))
    {
        return -1;
    }

    return nDayCnt;
}