[프로그래머스] 미로 탈출

---

🔗 문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/159993?language=cpp#

프로그래머스

---

반응형

728x90

👩‍💻 코드

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

using namespace std;

struct position{
    int x;
    int y;
    int count;
};

int BFS(vector<string> &maps, position start, char target){
    int width = maps.size();
    int height = maps[0].size();
    vector<vector<bool>> visited(width, vector<bool> (height, false));
    queue<position> q;
    int nextX[4] = { 0, 1, 0, -1};
    int nextY[4] = { 1, 0, -1, 0};

    q.push({start.x, start.y, 0});
    visited[start.x][start.y] = true;

    while(!q.empty()){
        position pos = q.front();
        int x = pos.x;
        int y = pos.y;
        int count = pos.count;
        char road = maps[x][y];
        q.pop();

        if(road == target){
            return count;
        }

        for(int i=0; i<4; i++){
            int newX = x + nextX[i];
            int newY = y + nextY[i];

            if(newX < width && newX >= 0 && newY < height && newY >= 0 && !visited[newX][newY] && maps[newX][newY] != 'X'){
                q.push({newX, newY, count + 1});
                visited[newX][newY] = true;
            }
        }
    }

    return -1;
}

int solution(vector<string> maps) {
    position start;
    position lever;
    position exit;

    for (int i = 0; i < maps.size(); i++) {
        for (int j = 0; j < maps[0].size(); j++) {
            if (maps[i][j] == 'S'){
                start = {i, j, 0};
            }

            if (maps[i][j] == 'L'){
                lever = {i, j, 0};
            }

            if (maps[i][j] == 'E'){
                exit = {i, j, 0};
            }
        }
    }

    int toLever = BFS(maps, start, 'L');

    if (toLever == -1) {
        return -1;
    }

    int toExit = BFS(maps, lever, 'E');

    if (toExit == -1) {
        return -1;
    }

    return toLever + toExit;
}

---

📝 풀이

시작 지점에서 레버까지, 레버에서 출구까지의 최단 경로를 BFS 알고리즘으로 구합니다.

둘 중 하나라도 경로를 찾지 못 하면 -1을 return 합니다.