백준 2178 : 미로 탐색

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

2178번: 미로 탐색

 

#include <iostream>
#include <string>
#include <vector>
#include <queue>
 
struct coord
{
    int y;
    int x;
};
 
int N, M;
int dy[4] = { 1, 0, -1, 0 };
int dx[4] = { 0, 1, 0, -1 };
 
int ans = 987654321;
int maze[100][100];
 
void input()
{
    std::cin >> N >> M;
    for (int y = 0; y < N; ++y)
    {
        for (int x = 0; x < M; ++x)
        {
            scanf("%1d", &maze[y][x]);
            maze[y][x] = -maze[y][x];
        }
    }
}
 
void pf()
{
    std::cout << '\n';
    for (int y = 0; y < N; ++y)
    {
        for (int x = 0; x < M; ++x)
        {
            std::cout << maze[y][x] << ' ';
        }
        std::cout << '\n';
    }
}
 
bool border_check(int y, int x)
{
    return (-1 < y && -1 < x) && (y < N&& x < M);
}
 
void solve()
{
    std::queue<coord> bfsQueue;
    bfsQueue.push({ 0, 0 });
    maze[0][0] = 1;
    while (bfsQueue.empty() == false)
    {
        //pf();
        coord pos = bfsQueue.front();
        if (pos.y == N - 1 && pos.x == M - 1)
        {
            return;
        }
        bfsQueue.pop();
 
        for (int i = 3; i >= 0; --i)
        {
            if (border_check(dy[i] + pos.y, dx[i] + pos.x) && maze[dy[i] + pos.y][dx[i] + pos.x] != 0)
            {
                //if (maze[dy[i] + pos.y][dx[i] + pos.x] == -1 || maze[pos.y][pos.x] < maze[dy[i] + pos.y][dx[i] + pos.x])
                if (maze[dy[i] + pos.y][dx[i] + pos.x] == -1)
                {
                    maze[dy[i] + pos.y][dx[i] + pos.x] = maze[pos.y][pos.x] + 1;
                    bfsQueue.push({ dy[i] + pos.y, dx[i] + pos.x });
                }
            }
        }
    }
}
 
 
void output()
{
    std::cout << maze[N - 1][M - 1];
}
 
int main()
{
    input();
    solve();
    output();
    return 0;
}

 

 

BFS는 너비 우선이기 때문에 겉에서부터 얕게 깐다는걸 필히 마음속에 새겨놔야 한다

 

즉, 목적된 값을 찾는다면 그 값이 바로 어떠한 거리의 최솟값인 경우가 태반이기 때문에

 

다른 조건이 구태여 의미가 없어지는 경우가 생긴다

 

69번 라인의 저 주석처럼..