프로그래머스 미로 탈출

해당 문제는 bfs로 풀이했다

 

출발 지점에서 도착 지점까지 가되, 레버가 있는 곳을 경유해서 가야하기 때문에

결국에는 레버가 있는 곳을 시작 지점으로 삼아서 bfs를 돌면서

출발 지점과 도착지점 각각까지의 최단경로를 구한 뒤 더해주면 될 것 같다고 판단했다.

그렇게 하면 BFS를 한번만 돌아서 문제를 해결할 수 있다.

 

내 풀이

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

bool VISIT[100][100];
int row, col;

bool S = false, E = false; // 각각, 시작점과 끝점 도착 여부에 대한 불리언
int GOAL = 0; // 총 거리

int mx[4] = {0, 0, 1, -1};
int my[4] = {1, -1, 0, 0};

using namespace std;

void bfs(vector<string>& map, int x, int y) {
    
    queue<pair<int, pair<int, int>>> que;
    que.push({0, {x, y}});
    VISIT[x][y] = true;
    
    while(!que.empty()) {
        
        int xx = que.front().second.first;
        int yy = que.front().second.second;
        int dep = que.front().first;
        
        que.pop();
        
        
        for(int i = 0; i < 4; i++) {
            
            int tx = xx + mx[i];
            int ty = yy + my[i];
            
            if(tx < 0 || ty < 0 || tx >= row || ty >= col)
                continue;
            
            if(map[tx][ty] != 'X' && !VISIT[tx][ty]) {
                
                que.push({dep + 1, {tx, ty}});
                VISIT[tx][ty] = true;
                
                if(map[tx][ty] == 'S') {
                    GOAL += (dep + 1);
                    S = true;
                }
                if(map[tx][ty] == 'E') {
                    GOAL += (dep + 1);
                    E = true;
                }
            }   
        }   
    }
}

int solution(vector<string> maps) {
    
    row = maps.size();
    col = maps[0].size();
    
    
    for(int i = 0; i < row; i++) {
        for(int j = 0; j < col; j++) {
            
            if(maps[i][j] == 'L') {
                
                // 레버 위치를 찾았다.
                bfs(maps, i, j);
                
                if(S && E)
                    return GOAL;
                else
                    return -1;
            }
        }
    }
}