개발기록장

미로 탈출

5 min read

문제 링크
난이도 : Lv. 2

문제 내용

문제 설명

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

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

제한사항
  • 5 ≤ maps의 길이 ≤ 100
    • 5 ≤ maps[i]의 길이 ≤ 100
    • maps[i]는 다음 5개의 문자들로만 이루어져 있습니다.
      • S : 시작 지점
      • E : 출구
      • L : 레버
      • O : 통로
      • X : 벽
    • 시작 지점과 출구, 레버는 항상 다른 곳에 존재하며 한 개씩만 존재합니다.
    • 출구는 레버가 당겨지지 않아도 지나갈 수 있으며, 모든 통로, 출구, 레버, 시작점은 여러 번 지나갈 수 있습니다.
입출력 예
mapsresult
[“SOOOL”,“XXXXO”,“OOOOO”,“OXXXX”,“OOOOE”]16
[“LOOXS”,“OOOOX”,“OOOOO”,“OOOOO”,“EOOOO”]-1
입출력 예 설명

입출력 예 #1

주어진 문자열은 다음과 같은 미로이며

image1

다음과 같이 이동하면 가장 빠른 시간에 탈출할 수 있습니다.

image2

4번 이동하여 레버를 당기고 출구까지 이동하면 총 16초의 시간이 걸립니다. 따라서 16을 반환합니다.

입출력 예 #2

주어진 문자열은 다음과 같은 미로입니다.

image3

시작 지점에서 이동할 수 있는 공간이 없어서 탈출할 수 없습니다. 따라서 -1을 반환합니다.

문제 분석

일단 레버로 가는 빠른 가장 빠른 길로 갔다가, 레버에서 Exit까지 가장 빨리 가는 길로 가야함

결과적으로 시작점→레버로 bfs 한 번 하고, 레버→Exit 로 bfs 한 번 더 하면 됨

작성한 코드

#include <string>
#include <vector>
#include <queue>
 
using namespace std;
 
struct Point
{
    int y, x, cnt;
};
 
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, -1, 0, 1};
int n, m; // size
 
bool isInMap(int y, int x) 
{
    return 0 <= y && y < n && 0 <= x && x < m;
}
 
Point findStartPoint(char start, vector<string> &maps)
{
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            if(maps[i][j] == start)
            {
                return {i, j, 0};
            }
        }
    }
    return {-1, -1, -1};
}
 
int bfs (char start, char end, vector<string> &maps)
{
    bool visited[101][101] = {false};
    queue<Point> q;
    
    q.push(findStartPoint(start, maps));
    
    while(!q.empty())
    {
        Point current = q.front();
        q.pop();
        
        if(maps[current.y][current.x] == end)
        {
            return current.cnt;
        }
        
        for(int i = 0; i < 4; i++)
        {
            int ny = current.y + dy[i];
            int nx = current.x + dx[i];
            if(isInMap(ny, nx) && !visited[ny][nx] && maps[ny][nx] != 'X')
            {
              q.push({ny, nx, current.cnt + 1});
                visited[ny][nx] = true;
            }
        }
    }
    
    return -1;
}
 
 
int solution(vector<string> maps) {
    n = maps.size();
    m = maps[0].size();
    
    // go to lever (?)
    int distToLever = bfs('S', 'L', maps);
    if(distToLever == -1) return -1;
    
    // go to exit
    int distToExit = bfs('L', 'E', maps);
    if(distToExit == -1) return -1;
    return distToLever + distToExit;
}

그래프 뷰