미로 찾기 - 2178번 백준

문제

문제 난이도 : 실버 1

문제 분류 : Graph , DFS, BFS

---

문제 풀이 및 코드

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;



void Init()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

int main()
{
    //Initialize
    Init();
    //Input
    int W, H;
    cin >> H >> W;
    vector<vector<int>> Map(H, vector<int>(W,false));
    vector<vector<int>> Visited(H, vector<int>(W, false));
    for (int i = 0; i < H; i++)
    {
        string s;
        cin >> s;
        for (int j = 0; j < W; ++j)
        {
            if (s[j] == '1')
            {
                Map[i][j] = 1;
                Visited[i][j] = 0;
            }
            else
            {
                Map[i][j] = 0;
                Visited[i][j] = 1;
            }
        }
    }
    
    queue<vector<int>> q;
    q.push({ 0,0,0 });
    int ReturnVal = 2100000000;
    while (!q.empty())
    {
        vector<int> vp = q.front();
        q.pop();
        if (vp[0] == H -1 && vp[1] == W - 1)
        {
            ReturnVal = min(ReturnVal, vp[2]);
            
        }
        if (Visited[vp[0]][vp[1]] == true) continue;
        Visited[vp[0]][vp[1]] = true;

        if (vp[0] > 0)
        {
            q.push({ vp[0] - 1, vp[1], vp[2] + 1 });
        }
        if (vp[1] > 0)
        {
            q.push({ vp[0], vp[1] - 1, vp[2] + 1 });
        }
        if (vp[0] < H - 1)
        {
            q.push({ vp[0] + 1, vp[1], vp[2] + 1 });
        }
        if (vp[1] < W - 1)
        {
            q.push({ vp[0] , vp[1] + 1, vp[2] + 1 });
        }


    }

    cout << ReturnVal + 1;
    

}