[프로그래머스 Lv.2] 미로 탈출

[문제]

https://school.programmers.co.kr/learn/courses/30/lessons/159993

 

 

[풀이]

 

BFS를 두 번 실시하면 된다. 먼저 시작 지점부터 레버로 갈 수 있는지, 그 다음에는 레버로부터 도착 지점으로 갈 수 있는지를 확인한다.

#include <string>
#include <vector>
#include <queue>

using namespace std;


int BFS(const vector<string>& _maps, pair<int, int> _StartCoord, char _Target)
{
    int Height = _maps.size();
    int Width = _maps[0].size();
    vector<vector<int>> Visited(Height, vector<int>(Width, 0));

    int SearchY[4] = { -1, 1, 0, 0 };
    int SearchX[4] = { 0, 0, -1, 1 };

    queue<pair<int, int>> Que;
    Que.push(_StartCoord);
    Visited[_StartCoord.first][_StartCoord.second] = 1;

    while (!Que.empty())
    {
        int CurY = Que.front().first;
        int CurX = Que.front().second;
        Que.pop();

        if (_maps[CurY][CurX] == _Target)
        {
            return Visited[CurY][CurX] - 1;
        }

        for (int Dir = 0; Dir < 4; ++Dir)
        {
            int NextY = CurY + SearchY[Dir];
            int NextX = CurX + SearchX[Dir];

            if (NextY < 0 || NextY >= Height || NextX < 0 || NextX >= Width)
            {
                continue;
            }

            if (_maps[NextY][NextX] != 'X' && Visited[NextY][NextX] == 0)
            {
                Visited[NextY][NextX] = Visited[CurY][CurX] + 1;
                Que.push({ NextY, NextX });
            }
        }
    }

    return -1;
}

// 통로들 중 한 칸에는 미로를 빠져나가는 문이 있는데, 이 문은 레버를 당겨서만 열 수 있습니다.
// 출발 지점에서 먼저 레버가 있는 칸으로 이동하여 레버를 당긴 후 미로를 빠져나가는 문이 있는 칸으로 이동
// 이때 아직 레버를 당기지 않았더라도 출구가 있는 칸을 지나갈 수 있습니다.
// 미로에서 한 칸을 이동하는데 1초가 걸린다고 할 때, 최대한 빠르게 미로를 빠져나가는데 걸리는 시간
int solution(vector<string> maps)
{
    pair<int, int> StartPos;
    pair<int, int> LeverPos;
    pair<int, int> ExitPos;

    for (int Y = 0; Y < maps.size(); ++Y)
    {
        for (int X = 0; X < maps[0].size(); ++X)
        {
            if (maps[Y][X] == 'S')
            {
                StartPos = { Y, X };
            }
            else if (maps[Y][X] == 'L')
            {
                LeverPos = { Y, X };
            }
            else if (maps[Y][X] == 'E')
            {
                ExitPos = { Y, X };
            }
        }
    }

    int ToLeverTime = BFS(maps, StartPos, 'L');
    if (ToLeverTime == -1)
    {
        return -1;
    }

    int ToExitTime = BFS(maps, LeverPos, 'E');
    if (ToExitTime == -1)
    {
        return -1;
    }

    return ToLeverTime + ToExitTime;
}

int main()
{
    vector<string> maps = { "SOOOL","XXXXO","OOOOO","OXXXX","OOOOE" };
    solution(maps);

    return 0;
}