[C++] Programmers | 미로 탈출

미로 탈출

프로그래머스

---

✍🏻 풀이

문제의 미로를 탈출하려면 크게 두 가지 단계를 거쳐야 한다.

1. 시작 지점에서 레버가 있는 곳까지 간다.
2. 레버가 있는 곳에서 출구까지 간다.

미로를 탈출하는데 필요한 '최소 시간'을 구해야 하므로

BFS(너비 우선 탐색) 알고리즘을 사용하였다.

 

⭐️ 이 문제에서 주의할 점은, 레버를 당기지 않으면 출구가 열리지 않기 때문에

두 단계에서 각각 BFS를 돌리고 둘 중 하나라도 만족하지 못 하면 -1을 return 해야한다.

---

✅ Accept Code

// programmers week6-3
// 미로 탈출
// BFS

#include <bits/stdc++.h>


using namespace std;

pair<int, int> S, L;
int di[4] = {0, 0, 1, -1};
int dj[4] = {1, -1, 0, 0};
bool visited[100][100];

int BFS1(vector<string> maps) { // 출발 -> 레버
    memset(visited, false, sizeof(visited));
    queue<pair<pair<int, int>, int>> Q;
    Q.push({S, 0});
    visited[S.first][S.second] = true;

    while (!Q.empty()) {
        int cur_i = Q.front().first.first;
        int cur_j = Q.front().first.second;
        int cur_time = Q.front().second;
        Q.pop();

        for (int idx = 0; idx < 4; idx++) {
            int new_i = cur_i + di[idx];
            int new_j = cur_j + dj[idx];

            if (new_i < 0 || new_i > maps.size() - 1 || new_j < 0 || new_j > maps[0].size() - 1) continue;
            if (maps[new_i][new_j] == 'X' || visited[new_i][new_j]) continue;
            if (maps[new_i][new_j] == 'L') {
                return cur_time + 1;
            }
            visited[new_i][new_j] = true;
            Q.push({{new_i, new_j}, cur_time + 1});
        }
    }
    return -1;
}

int BFS2(vector<string> maps) { // 레버 -> 출구
    memset(visited, false, sizeof(visited));
    queue<pair<pair<int, int>, int>> Q;
    Q.push({L, 0});
    visited[L.first][L.second] = true;

    while (!Q.empty()) {
        int cur_i = Q.front().first.first;
        int cur_j = Q.front().first.second;
        int cur_time = Q.front().second;
        Q.pop();

        for (int idx = 0; idx < 4; idx++) {
            int new_i = cur_i + di[idx];
            int new_j = cur_j + dj[idx];

            if (new_i < 0 || new_i > maps.size() - 1 || new_j < 0 || new_j > maps[0].size() - 1) continue;
            if (maps[new_i][new_j] == 'X' || visited[new_i][new_j]) continue;
            if (maps[new_i][new_j] == 'E') {
                return cur_time + 1;
            }
            visited[new_i][new_j] = true;
            Q.push({{new_i, new_j}, cur_time + 1});
        }
    }
    return -1;
}


int solution(vector<string> maps) {

    for (int i = 0; i < maps.size(); i++) {
        for (int j = 0; j < maps[i].size(); j++) {
            if (maps[i][j] == 'S') {
                S.first = i;
                S.second = j;
            } else if (maps[i][j] == 'L') {
                L.first = i;
                L.second = j;
            }
        }
    }

    int first = BFS1(maps);
    if (first == -1) return -1;
    int second = BFS2(maps);
    if (second == -1) return -1;

    return first + second;
}