1 문제

BFS를 이용해 미로에서 최단 경로를 찾는 문제

2 Idea

이미 들렸던 곳인 경우를 확인하기 위해 visit 체크
Queue에 다음으로 순회할 곳을 qush
Queue가 empty가 되기 전까지 계속 탐색

3 Code

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

#include <iostream>
#include <vector>
#include <queue>

typedef struct{
    int i;
    int j;
    int time;
} pos;

const std::vector<std::vector<int>> DIRECTION = {
    {1, 0},
    {-1, 0},
    {0, 1},
    {0, -1},
    };

int FindMinWay(const std::vector<std::vector<bool>>& v, const int N, const int M){
    int answer = -1;

    //make visit
    std::vector<std::vector<bool>> visit(N+1, std::vector<bool>(M+1, false));
    
    visit[1][1] = true;
    
    //make q
    std::queue<pos> q;
    q.push({1, 1, 1});

    while (!q.empty()){
        const auto now = q.front();
        q.pop();
        
        const int i = now.i;
        const int j = now.j;
        const int time = now.time;

        for (const auto& dir : DIRECTION){
            const int i_new = i+dir[0];
            const int j_new = j+dir[1];

            if ((i_new == N) && (j_new == M)){
                answer = time+1;

                return answer;
            }

            if ((i_new > N) || (j_new > M) || (i_new < 1) || (j_new < 1)){
                //out of miro

                continue;
            }
            else if (visit[i_new][j_new]){
                //already visited

                continue;
            }
            else if (v[i_new][j_new]){
                visit[i_new][j_new] = true;
                q.push({i_new, j_new, time+1});
            }
        }
    }

    return answer;
}

int main(){
    int N = 0;
    int M = 0;

    std::cin >> N >> M;

    //make v
    std::vector<std::vector<bool>> v(N+1, std::vector<bool>(M+1, false));
        //ignore 0

    for (int i=1; i<=N; ++i){
        std::string temp;

        std::cin >> temp;

        for (int j=0; j<M; ++j){
            if (temp[j] == '1'){
                v[i][j+1] = true;
            }
        }
    }

    std::cout << FindMinWay(v, N, M) << std::endl;

    return 0;
}