미로 탐색

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

• moveCnt를 증가시키고 확장을 하기 전에 큐의 size를 확인해서 진행했어야 한다

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int row;
int col;

vector<string> maze;
vector<vector<bool>> visited;

int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};

void bfs()
{
    int moveCnt=0;
    queue<pair<int,int>> q;

    moveCnt++;
    visited[0][0] = true;
    q.push(make_pair(0,0));

    while(!q.empty())
    {
        size_t qsize = q.size();
        moveCnt++;
        for(int move=0; move<qsize; move++)
        {
            int curR = q.front().first;
            int curC = q.front().second;
            q.pop();

    
            for(int d=0; d < 4; d++)
            {
                int nextR = curR + dx[d];
                int nextC = curC + dy[d];

                if(nextR < 0 || nextR >= row || nextC < 0 || nextC >= col)
                {
                    continue;
                }

                if(maze[nextR].at(nextC) == '0' || visited[nextR][nextC] == true)
                {
                    continue;
                }

                if(nextR==row-1 && nextC==col-1)
                {
                    cout << moveCnt;
                    return;
                }

                visited[nextR][nextC] = true;            
                q.push(make_pair(nextR, nextC));
            }
        }
    }
}

int main()
{
    cin >> row >> col;

    maze.resize(row);
    visited.resize(row, vector<bool>(col, false));

    for(int i=0; i<row; i++)
    {
        cin >> maze[i];
    }

    bfs();
}