[Programmers] Lv2. 미로 탈출 | C++

🔗문제 보러가기

프로그래머스

 

 

👨‍💻풀이 과정

 

처음엔 DFS로 접근했지만 시간 초과가 떴습니다. 시간을 줄이기 위해 목표(레버 혹은 출구) 지점 방향으로 이동하게끔 알고리즘을 다시 짰지만, 가는 길목이 막혀서 다른 길로 돌아가야 할 때 방향이 달라져 DFS 탐색이 끝나버리는 문제가 발생했었습니다.

 

고민을 많이 해봤지만 답이 보이지 않아 해당 전략은 포기하고, BFS로 갈아타서 풀게 되었습니다. BFS로 푼 적이 별로 없어 코드 작성하는 게 조금 어색했는데, 이 참에 한 번 연습해 봐야겠습니다.

 

✏️소스 코드 및 결과

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

int rowDirection[4] = { -1, 1, 0, 0 };
int columnDirection[4] = { 0, 0, -1, 1 };

class Info
{
public:
    Info(int row, int column, int currentTime) : _row(row), _column(column), _currentTime(currentTime) { }
    int _row;
    int _column;
    int _currentTime;
};

map<char, pair<int, int>> GetLabelPositions(const vector<string>& maps)
{
    map<char, pair<int, int>> result;

    for (int row = 0; row < maps.size(); row++)
    {
        for (int column = 0; column < maps[row].length(); column++)
        {
            char label = '@';

            if (maps[row][column] == 'S')
                label = 'S';
            else if (maps[row][column] == 'E')
                label = 'E';
            else if (maps[row][column] == 'L')
                label = 'L';

            if (label != '@')
                result.insert(make_pair(label, make_pair(row, column)));
        }
    }

    return result;
}


int CalculateTimeWithBFS(const vector<string>& maps, Info start, Info end, bool& isFindTarget)
{
    vector<vector<bool>> visited(maps.size(), vector<bool>(maps[0].length(), false));
    int minTime = 2147483647;
    queue<Info> _queue;

    _queue.push(start);
    visited[start._row][start._column] = true;

    while (!_queue.empty())
    {
        Info current = _queue.front();
        _queue.pop();

        if ((current._row == end._row) and (current._column == end._column))
        {
            isFindTarget = true;
            minTime = min(minTime, current._currentTime);
        }

        for (int i = 0; i < 4; i++)
        {
            int nextRow = current._row + rowDirection[i];
            int nextColumn = current._column + columnDirection[i];

            if (nextRow < 0 or nextRow >= maps.size() or nextColumn < 0 or nextColumn >= maps[0].length())
                continue;
            if (visited[nextRow][nextColumn] or maps[nextRow][nextColumn] == 'X')
                continue;

            _queue.push(Info(nextRow, nextColumn, current._currentTime + 1));
            visited[nextRow][nextColumn] = true;
        }
    }

    if (!isFindTarget)
        return -1;
    return minTime;
}


int FindMinEscapeMazeTime(map<char, pair<int, int>>& labelPositions, const vector<string>& maps)
{
    int result = 0;
    bool isFindTarget = false;
    auto start = labelPositions['S'];
    auto lever = labelPositions['L'];
    auto exit = labelPositions['E'];

    int findingLeverMinTime = CalculateTimeWithBFS(maps, Info(start.first, start.second, 0), Info(lever.first, lever.second, 0), isFindTarget);
    if (findingLeverMinTime == -1)
        return -1;


    isFindTarget = false;
    int findingExitMinTime = CalculateTimeWithBFS(maps, Info(lever.first, lever.second, 0), Info(exit.first, exit.second, 0), isFindTarget);
    if (findingExitMinTime == -1)
        return -1;

    return findingLeverMinTime + findingExitMinTime;
}

int solution(vector<string> maps) {
    map<char, pair<int, int>> labelPositions = GetLabelPositions(maps);
    int answer = FindMinEscapeMazeTime(labelPositions, maps);
    return answer;
}

 

제출 결과