미로 탈출

프로그래머스 - 미로 탈출

문제

---

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

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

💡Idea

1. 어디서 출발해야할까?
   → maps를 돌면서 시작지점(S)을 찾아 queue 에 push하자 !
2. 최소 시간을 어떻게 구할까?
   → 시간을 저장하는 check 배열을 생성하여 queue의 front 값 + 1을 해준다.
   → 이때, 이미 방문했다면 건너뜀

[ SourceCode ]

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

using namespace std;

int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 상, 하, 좌, 우

int bfs(vector<string> maps, char dest, pair <int, int> now) {
    queue <pair<int, int>> tmp; // 방문 좌표
    vector <vector<int>> check(100, vector<int>(100, -1)); // 최소 시간
    check[now.first][now.second] = 0;
    tmp.push(now);
   
    while(!tmp.empty()) {
        int x = tmp.front().first;
        int y = tmp.front().second;
        tmp.pop();
       
        if(maps[x][y] == dest) { // 도착한 경우(레버 or 출구)
            return check[x][y];
        }
       
        for(int i=0; i<4; i++) {
            int nx = x + dir[i][0];
            int ny = y + dir[i][1];
           
            if(nx < 0 || nx >= maps.size() || ny < 0 || ny >= maps[0].length()) continue; // 범위 벗어남
            if(maps[nx][ny] == 'X' || check[nx][ny] != -1) continue; // 벽일 경우
           
            tmp.push({nx, ny});
            check[nx][ny] = check[x][y] + 1;
        }
    }
   
    return -1;
}

int solution(vector<string> maps) {
    pair <int, int> start, lever;
    for(int i=0; i<maps.size(); i++) {
        for(int j=0; j<maps[0].length(); j++) {
            if(maps[i][j] == 'S') { // 시작 지점
                start = {i, j};
            }
            if(maps[i][j] == 'L') { // 레버 위치
                lever = {i, j};
            }
        }
    }
   
    int dist1 = bfs(maps, 'L', start);
    if(dist1 == -1) return -1; // 레버로 갈 수 없는 경우
    int dist2 = bfs(maps, 'E', lever);
    if(dist2 == -1) return -1; // 출구로 갈 수 없는 경우
    return dist1 + dist2;
}

Feedback

---

1. 처음에 문제를 제대로 이해하지 못했다.
   - 레버를 당기지 않았더라도 출구가 있는 칸을 지나갈 수 있습니다.
   → 당기지 않아도 탈출할 수 있다고 착각함,,
2. 방문 좌표들을 담는 queue를 초기화하지 않아도 된다고 판단했다.

• 도착했을 때 queue에 남아있을 수 있다는 것을 고려해야한다.
  → bfs 안에서 queue 생성함으로써 해결 !