프로그래머스 미로 탈출 [Lv. 2] (C++)

프로그래머스

미로를 나타낸 문자열 배열 maps가 매개변수로 주어질 때, 미로를 탈출하는데 필요한 최소 시간을 return 하는 solution 함수를 완성해주세요. 

 

풀이 방법

시작 지점에서 출구로 가는 가장 짧은 길을 찾을 때, 레버를 반드시 거쳐서 가야합니다.

그렇기 때문에 입구 -> 출구의 거리만 찾는게 아니라 입구->레버의 거리와 레버->출구까지의 거리를 찾고 두 거리를 더해서 반환해주면 됩니다.

 

int solution(vector<string> maps) {
    int answer = 0;
    
    pair<int, int> sPos, lPos, ePos;
    
    for (int i = 0; i < maps.size(); i++)
        for (int j = 0; j < maps[i].size(); j++){

            if (maps[i][j] == 'L')
                lPos = make_pair(i, j);
            else if (maps[i][j] == 'E')
                ePos = make_pair(i, j);
            else if (maps[i][j] == 'S')
                sPos = make_pair(i, j);
        }

    int toL = GetCost(maps, sPos, lPos);
    int toE = GetCost(maps, lPos, ePos);
    return (toL == -1 || toE == -1) ? -1 : toL + toE;
}

 

 

거리를 계산하는 함수는 아래와 같은 너비우선탐색을 이용하여 찾을 수 있습니다.

int dy[4] = {1, -1, 0, 0};
int dx[4] = {0, 0, 1, -1};
int GetCost(vector<string>& map, pair<int, int> start, pair<int, int> end)
{
    vector<vector<bool>> visited(map.size(), vector<bool>(map[0].size()));
    queue<pair<pair<int, int>, int>> q;
    q.push({start, 0});
    

    int ret = -1;
    while(!q.empty())
    {
        auto[info, cost] = q.front(); q.pop();
        auto[cy, cx] = info;
        visited[cy][cx] = true;
        
        if (cy == end.first && cx == end.second){
            ret = ret == -1 ? cost : min(ret, cost);
            continue;            
        }
        
        for (int i = 0; i < 4; i++)
        {
            auto [ny, nx] = make_pair(cy + dy[i], cx + dx[i]);
            if (ny < 0 || ny >= map.size() || 
                nx < 0 || nx >= map[0].size() || 
                map[ny][nx] == 'X' || visited[ny][nx])
                continue;
            
            q.push({{ny, nx}, cost+1});
        }
        
    }
    return ret;
}

 

하지만 위 코드는 시간초과가 발생하기 때문에 다익스트라 처럼 탐색 속도가 더 빠른 알고리즘을 이용해주면 됩니다.

 

정답 코드

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

using namespace std;

int dy[4] = {1, -1, 0, 0};
int dx[4] = {0, 0, 1, -1};
int GetCost(vector<string>& map, pair<int, int> start, pair<int, int> end)
{
    vector<vector<int>> cost(map.size(), vector<int>(map[0].size(), 
                                                     numeric_limits<int>::max()));
    priority_queue<pair<int, pair<int, int>>, 
                    vector<pair<int, pair<int, int>>>, greater<>> pq;

    cost[start.first][start.second] = 0;
    pq.push({0, start});

    while (!pq.empty())
    {
        auto [currentCost, info] = pq.top(); pq.pop();
        auto [cy, cx] = info;

        if (cy == end.first && cx == end.second)
            return currentCost;

        for (int i = 0; i < 4; i++)
        {
            int ny = cy + dy[i];
            int nx = cx + dx[i];

            if (ny < 0 || ny >= map.size() || 
                nx < 0 || nx >= map[0].size() || 
                map[ny][nx] == 'X')
                continue;

            int newCost = currentCost + 1;

            if (newCost < cost[ny][nx])
            {
                cost[ny][nx] = newCost;
                pq.push({newCost, {ny, nx}});
            }
        }
    }

    return -1; // 목표 지점에 도달할 수 없는 경우
}

int solution(vector<string> maps) {
    int answer = 0;
    
    pair<int, int> sPos, lPos, ePos;
    
    for (int i = 0; i < maps.size(); i++)
        for (int j = 0; j < maps[i].size(); j++){

            if (maps[i][j] == 'L')
                lPos = make_pair(i, j);
            else if (maps[i][j] == 'E')
                ePos = make_pair(i, j);
            else if (maps[i][j] == 'S')
                sPos = make_pair(i, j);
        }

    int toL = GetCost(maps, sPos, lPos);
    int toE = GetCost(maps, lPos, ePos);
    return (toL == -1 || toE == -1) ? -1 : toL + toE;
}