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

https://school.programmers.co.kr/learn/courses/30/lessons/159993

프로그래머스

문제 유형 : dfs / bfs

문제 난이도 : Level 2

 

문제 설명

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

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

 

풀이

bfs를 이용하여서 시작 지점 - 레버, 레버 - 도착지점의 거리를 구한다.

주의할 점은, 거리를 구할 때 카운트에 유의해야 하고, X를 제외한 모든 방문하지 않은 칸은 추가가 가능하다는 것이다(S -> L을 갈때, E를 지나갈 수 있다!, L -> E를 갈 때, S를 지나갈 수 있다!)

 

코드

C++

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

using namespace std;

vector<int> dx = {1, -1, 0, 0};
vector<int> dy = {0, 0, 1, -1};

int bfs(vector<string>& maps, pair<int, int> from, pair<int, int> to) {
    vector<vector<bool>> visited(maps.size(), vector<bool>(maps[0].size(), false));
    queue<pair<int, int>> q;
    visited[from.first][from.second] = true;
    q.push(from);

    int cnt = 0;
    while (!q.empty()) {
        int currentSize = q.size();
        for (int t = 0; t < currentSize; t++) {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();

            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                if (nx >= 0 && nx < visited.size() && ny >= 0 && ny < visited[0].size()) {
                    if(nx == to.first && ny == to.second) return ++cnt;
                    if (maps[nx][ny] == 'X') continue;
                    if (!visited[nx][ny]) {
                        visited[nx][ny] = true;
                        q.push(make_pair(nx, ny));
                    }
                }
            }
        }
        cnt++;
    }

    return -1;
}


int solution(vector<string> maps) {
    pair<int, int> s; //출발점
    pair<int, int> l; //레버
    pair<int, int> e; //목적지

    for(int i = 0; i < maps.size(); i++) {
        for(int j = 0; j < maps[i].size(); j++) {
            if(maps[i][j] == 'S') {
                s = {i, j};
            } else if(maps[i][j] == 'L') {
                l = {i, j};
            } else if(maps[i][j] == 'E') {
                e = {i, j};
            }
        }
    }

    int to_lever = bfs(maps, s, l);
    if(to_lever == -1) return -1;
    int to_exit = bfs(maps, e, l);
    if(to_exit == -1) return -1;

    return to_lever + to_exit;
}