[프로그래머스] 연습문제>>미로 탈출

• 미로 탈출

문제 설명

1 x 1 크기의 칸들로 이루어진 직사각형 격자 형태의 미로에서 탈출하려고 합니다. 각 칸은 통로 또는 벽으로 구성되어 있으며, 벽으로 된 칸은 지나갈 수 없고 통로로 된 칸으로만 이동할 수 있습니다. 통로들 중 한 칸에는 미로를 빠져나가는 문이 있는데, 이 문은 레버를 당겨서만 열 수 있습니다. 레버 또한 통로들 중 한 칸에 있습니다. 따라서, 출발 지점에서 먼저 레버가 있는 칸으로 이동하여 레버를 당긴 후 미로를 빠져나가는 문이 있는 칸으로 이동하면 됩니다. 이때 아직 레버를 당기지 않았더라도 출구가 있는 칸을 지나갈 수 있습니다. 미로에서 한 칸을 이동하는데 1초가 걸린다고 할 때, 최대한 빠르게 미로를 빠져나가는데 걸리는 시간을 구하려 합니다.

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

---

제한사항

• 5 ≤ maps의 길이 ≤ 100
  • 5 ≤ maps[i]의 길이 ≤ 100
  • maps[i]는 다음 5개의 문자들로만 이루어져 있습니다.
    • S : 시작 지점
    • E : 출구
    • L : 레버
    • O : 통로
    • X : 벽
  • 시작 지점과 출구, 레버는 항상 다른 곳에 존재하며 한 개씩만 존재합니다.
  • 출구는 레버가 당겨지지 않아도 지나갈 수 있으며, 모든 통로, 출구, 레버, 시작점은 여러 번 지나갈 수 있습니다.

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1 }, INF = 987654321;

using namespace std;

int v[2][100][100]; //3차원배열
int solution(vector<string> maps) {
    queue<ti>q;//튜플 
    int N=maps.size(); //세로길이
    int M=maps[0].length();//가로길이
    pi E;//도착지점
    for(int i=0;i<maps.size();i++){
        for(int j=0;j<maps[i].length();j++){
            if(maps[i][j]=='S')
                q.push({0,i,j});
            if(maps[i][j]=='E')
                E={i,j};
        }
    }
    while(!q.empty()){ //BFS
        auto [k,y,x]=q.front();
        q.pop();
        rep(i,4){
            int ny=y+dy[i];
            int nx=x+dx[i];
            if(ny>=0 && ny<N && nx>=0 && nx<M && !v[k][ny][nx] && maps[ny][nx]!='X'){
                if(maps[ny][nx]=='L' && k==0){
                    v[1][ny][nx]=v[k][y][x]+1;
                    q.push({1,ny,nx});
                }
                else{
                    v[k][ny][nx]=v[k][y][x]+1;
                    q.push({k,ny,nx});
                }
            }
        }
    }
    int ret=v[1][E.first][E.second];
    return ret?ret:-1;
}