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

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

using namespace std;

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

int solution(vector<string> maps) {
    int answer = -1;
    bool flag = false;
    int y = 0, x = 0;
    
    queue<pair<int, int>>q;
    vector<vector<int>> v(maps.size(), vector<int>(maps[0].size(), 0));
    
    for(int i = 0; i<maps.size(); i++) //시작점 체크
    {
        for(int j=0; j<maps[0].size(); j++)
        {
            if(maps[i][j] == 'S')
            {
                y = i;
                x = j;
            }
        }
    }
    
    q.push({y, x});
    while(!q.empty())
    {
        auto [yy, xx] = q.front();
        q.pop();
        
        if(flag && 'E' == maps[yy][xx]) //레버 체크 여부 및 도착 체크
        {
            answer = v[yy][xx];
            break;
        }
        else if(!flag && 'L' == maps[yy][xx]) //레버 위치 및 시간 저장
        {
            flag = true;
            int lever = v[yy][xx];
            while (!q.empty()) q.pop(); 
            for (int i = 0; i < v.size(); i++) fill(v[i].begin(), v[i].end(), 0);

            v[yy][xx] = lever;
        }
        
        for(int i=0; i<4; i++)
        {
            int ny = yy + dy[i];
            int nx = xx + dx[i];
            
            if(nx < 0 || nx >= maps[0].size() || ny < 0 || ny >= maps.size()) continue;
            if(maps[ny][nx] != 'X' && v[ny][nx] == 0) //X 여부 및 중복 체크
            {
                q.push({ny, nx});
                v[ny][nx] = v[yy][xx] + 1; //시간 누적 저장
            }
        }
    }
    
    return answer;
}

 

살짝 응용된 BFS 문제이다.

일단 시작점 위치를 따로 저장하고 시작한다.

그리고 BFS를 위해 사용되는 큐 말고도 시간 누적 값을 담을 벡터도 선언해준다.

 

이제 레버 위치를 찾는다.

만약 레버 위치를 찾으면 레버를 활성화해주고, 현재 누적된 시간을 따로 저장해준다.

이어서 기존 큐와 벡터 값을 0으로 초기화 후에, 현재 위치에 해당하는 벡터 값에 누적 시간을 저장해준다.

 

이후에  BFS 탐색을 돌리면 기존에 저장된 레버 위치 시간을 이용해여 이어서 체크할 것이고,

결과적으로 레버 포함하여 총 누적 시간을 계산하게 된다.