[알고리즘 문제] 백준2178 - 미로탐색

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

2178번: 미로 탐색

시작지점에서 도착지점까지 이동하는데 최소이동거리를 구하는 문제이며 전형적인 bfs문제이다.

 

가로/높이의 크기가 100인데 bfs를 구현하기 위해서는 상/하/좌/우로 검사를 해줘야 한다. 그때 배열을 벗어나는 것을 검새해줘야 하는데, 나는 그냥 가로/높이에 한줄씩 추가해서 배열검사하는 부분을 뺏다.

#include <iostream>
#include <queue>

using namespace std;

struct Info
{
    int x;
    int y;
    int depth;
};

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

int main()
{

    int width, height;
    cin >> height >> width;

    int arr[200][200];

    for (int y = 1; y <= height; y++)
    {
        string s;
        cin >> s;
        for (int x = 0; x < s.size(); x++)
        {
            arr[y][x + 1] = s[x] - '0';
        }
    }

    queue<Info> que;

    Info info = {1, 1, 1};
    que.push(info);

    while (!que.empty())
    {
        Info cur = que.front();
        que.pop();

        if (cur.x == width && cur.y == height)
        {
            cout << cur.depth;
            return 0;
        }

        for (int i = 0; i < 4; i++)
        {
            int newX = cur.x + dx[i];
            int newY = cur.y + dy[i];

            if (arr[newY][newX] == 0) // 벽이면 pass
            {
                continue;
            }
            arr[newY][newX] = 0;
            que.push({newX, newY, cur.depth + 1});
        }
    }
    return 0;
}