[Algorithm] 프로그래머스 미로 탈출 - C++, BFS

프로그래머스

#include <string>
#include <vector>
#include <queue>
using namespace std;

const int MAX = 101;
int moveX[] = { 0, 0, 1, -1 };
int moveY[] = { 1, -1, 0, 0 };
int maxX, maxY;

bool IsOutRange(int x, int y)
{
    return (x < 0 || y < 0 || x >= maxX || y >= maxY);
}

int GetMinDistance(const pair<int, int>& from, const pair<int, int>& end, const vector<string>& maps)
{
    vector<vector<bool>> visit(maxY, vector<bool>(maxX, false));
    queue<pair<pair<int, int>, int>> q;
    q.push({from, 0});
    visit[from.first][from.second] = true;

    while (!q.empty())
    {
        auto curPos = q.front().first;
        auto curCount = q.front().second;
        q.pop();

        if(curPos == end)
        {
            return curCount;
        }

        for(int i = 0; i < 4; ++i)
        {
            int nextY = curPos.first + moveY[i];
            int nextX = curPos.second + moveX[i];

            if(IsOutRange(nextX, nextY) || visit[nextY][nextX]) continue;
            visit[nextY][nextX] = true;
            if(maps[nextY][nextX] == 'X')   continue;

            q.push({{nextY, nextX}, curCount + 1});
        }
    }
    return -1;
}


int solution(vector<string> maps) 
{
    maxY = maps.size();
    maxX = maps[0].size();
    pair<int, int> start, lever, exit;

    for(int y = 0; y < maxY; ++y)
    {
        for(int x = 0; x < maxX; ++x)
        {
            if(maps[y][x] == 'S')
                start = {y, x};
            else if (maps[y][x] == 'L')
                lever = {y, x};
            else if (maps[y][x] == 'E')
                exit = {y, x};
        }
    }

    auto distanceToLever{ GetMinDistance(start, lever, maps) };
    auto distanceToExit{ GetMinDistance(lever, exit, maps) };

    return (distanceToLever == -1 || distanceToExit == -1) ? -1 : distanceToExit + distanceToLever;
}

---

풀이법이 바로 떠올라 금방 풀이할 수 있었던 문제지만 한가지 실수로 조금 오래 걸렸네요.

 

일단 기본 알고리즘은 '시작지점에서 레버까지 최단거리 + 레버에서 도착지점까지 최단거리'를 구하는 것입니다. 이러면 간단하게 문제에서 원하는 거리를 보내줄 수 있습니다.

 

int GetMinDistance(const pair<int, int>& from, const pair<int, int>& end, const vector<string>& maps)
{
	bool visit[MAX][MAX];  // 이건 틀렸다!
    vector<vector<bool>> visit(maxY, vector<bool>(maxX, false));

다만 visit 체크를 위한 bool 배열을 처음에는 C 스타일 배열로 했다가 계속 틀렸습니다가 나왔습니다. 아무래도 초기화 되지 않아서 문제가 생긴것으로 판단하고 아래 2중 vector<bool>로 변경해서 풀이를 했습니다.