백준 : 2178번 미로 탐색(C++14)_BFS

핵심

입력 받은 2차원 배열(or백터)과 같은 사이즈로 출발점을 기준으로 각 칸으로 이동하는데 소요되는 Cost를 저장할 2차원 배열(or백터)를 하나 더 만든다

풀이

// 2020-05-21 wsshin

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

using namespace std;

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

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

    cin >> SizeY >> SizeX;

    vector<string> vecBoard;


    for (int i = 0; i < SizeY; i++)
    {
        string strTemp;
        cin >> strTemp;
        vecBoard.push_back(strTemp);
    }

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

    cout << nMaxCost << endl;

    return 0;
}




int Solution(int SizeY, int SizeX, vector<string> vecBoard)
{
    int dY[4] = { -1, 0, 1, 0 };
    int dX[4] = { 0, 1, 0, -1 };

    vector<vector<int>> vecVisited(SizeY, vector<int>(SizeX, 0));
    vector<vector<int>> vecCost(SizeY, vector<int>(SizeX, 0));

    queue<pair<int, int>> queue;

    vecVisited[0][0] = 1;
    int nCost = 1;
    vecCost[0][0] = nCost;

    queue.push(make_pair(0, 0));

    while (!queue.empty())
    {
        int nPivotY = queue.front().first;
        int nPivotX = queue.front().second;
        queue.pop();

        for (int i = 0; i < 4; i++)
        {
            int nPushY = nPivotY + dY[i];
            int nPushX = nPivotX + dX[i];

            if (nPushY < 0 || nPushY >= SizeY) continue;
            if (nPushX < 0|| nPushX >= SizeX) continue;
            if (vecVisited[nPushY][nPushX] == 1) continue;
            if (vecBoard[nPushY][nPushX] == '0') continue;

            int nCurCost = vecCost[nPivotY][nPivotX] + 1;

            vecVisited[nPushY][nPushX] = 1;
            vecCost[nPushY][nPushX] = nCurCost;
            queue.push(make_pair(nPushY, nPushX));
        }
    }

    return vecCost[SizeY - 1][SizeX - 1];
}