문제

https://school.programmers.co.kr/learn/courses/30/lessons/159993
직사각형 크기의 보드판에서 탈출을 해야한다.
이때, 'X' 가 있는 칸은 벽이여서 갈 수 없으며 탈출지점에 다다르기전에는 반드시 레버가 있는 칸에 들려 레버를 작동시켜야 한다.

최단거리로 탈출할 수 있는 거리를 출력해야 한다.
(탈출이 불가능한 경우 -1 출력)

풀이

최단거리를 찾는 문제여서 bfs로 푸는 것을 떠올렸다. 레버를 먼저 작동시켜야 탈출을 할 수 있으므로 시작점-레버 까지의 최단거리를 구하고 레버-탈출구 까지의 최단거리 이렇게 두 구간으로 나눠 각각의 구간의 최단거리를 구해 더해주는 방식으로 풀었다.
만일 둘 중 하나라도 도달할 수 없다면 탈출할 수 없는 것이므로 -1을 출력해주면 된다.

CODE

#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <iostream>
using namespace std;
typedef pair<int,int> pi;
int sr, sc, lr, lc, er, ec;
int maps_row, maps_col;
int dr[] = {0,0,-1,1}, dc[] = {-1,1,0,0};

bool isOverRange(int r, int c) {
    if(r < 0 || c < 0 || r >= maps_row || c >= maps_col)return true;
    return false;
}

bool isWall(char ch) {
    if(ch == 'X')return true;
    return false;
}

int bfs(int fr, int fc, int tr, int tc, vector<string> maps) {
    queue<pair<pi, int>> q;
    int chk[105][105] = {0, };

    q.push({{fr, fc}, 0});
    
    while(!q.empty()) {
        pair<pi,int> now = q.front();
        int r = now.first.first;
        int c = now.first.second;
        int d = now.second;
        q.pop();
        
        if(r == tr && c == tc) return d;
        
        for(int i=0;i<4;++i) {
            int nr = r + dr[i];
            int nc = c + dc[i];
            if(isOverRange(nr, nc) || chk[nr][nc] ||isWall(maps[nr][nc]))continue;
            q.push({{nr, nc}, d + 1});
            chk[nr][nc] = 1;
        }
    }
    return 0;
}

int solution(vector<string> maps) {
    int answer = 0;
    maps_row = maps.size();
    maps_col = maps[0].size();
    
    for(int i=0;i<maps_row;++i) {
        for(int j=0;j<maps_col;++j) {
            if(maps[i][j] == 'S') {
                sr = i;
                sc = j;
            }
            if(maps[i][j] == 'L') {
                lr = i;
                lc = j;
            }
            if(maps[i][j] == 'E') {
                er = i;
                ec = j;
            }
        }
    }
    
    int stol = bfs(sr, sc, lr, lc, maps);
    int ltoe = bfs(lr, lc, er, ec, maps);
    
    return answer = (stol * ltoe) ? stol + ltoe : -1;
}