[C++] Programmers Lv. 2 "미로 탈출"

🔵 문제 링크

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

프로그래머스

 

🔵 문제 접근

단순한 최단 거리를 찾는 문제이므로 bfs로 풀이할 수 있다.

이 문제의 특이한 점은 레버를 돌리고 출구로 가야 한다는 것이다.

따라서 시작점에서 레버까지의 최단 거리와 레버에서 출구까지의 최단 거리를 더하여 답을 반환하면 된다.

 

🔵 전체 코드

#include <string>
#include <vector>
#include <queue>
using namespace std;

// 따라서, 출발 지점에서 먼저 레버가 있는 칸으로 이동하여 레버를 당긴 후 미로를 빠져나가는 문이 있는 칸으로 이동하면 됩니다. 
// 미로를 탈출하는데 필요한 최소 시간을 return 하는 solution 함수를 완성해주세요. 만약, 탈출할 수 없다면 -1을 return 해주세요.

// 레버와 출구는 한 개씩만 존재
// 가장 빨리 레버로 가서, visited 초기화 한 후  바로 출구로

int dx[4] = { -1, 1, 0, 0 };    // 행 변화량
int dy[4] = { 0, 0, -1, 1 };    // 열 변화량

int bfs(const vector<string>& maps, pair<int, int> start, pair<int, int> end)
{
    const int ROW = maps.size();     // 행 (세로)
    const int COL = maps[0].size();  // 열 (가로)

    vector<vector<int>> visited(ROW, vector<int>(COL, -1));

    // 시작 시간 설정
    visited[start.first][start.second]++;

    queue<pair<int, int>> q;
    q.push(start);

    while (!q.empty())
    {
        int r = q.front().first;
        int c = q.front().second;
        q.pop();

        if (r == end.first && c == end.second)
            return visited[r][c];

        for (int i = 0; i < 4; i++)
        {
            int nr = r + dx[i];
            int nc = c + dy[i];

            if (nr < 0 || nc < 0 || nr >= ROW || nc >= COL) continue;
            if (maps[nr][nc] == 'X' || visited[nr][nc] != -1) continue;

            visited[nr][nc] = visited[r][c] + 1;
            q.push({ nr, nc });
        }
    }

    return -1;
}

int solution(vector<string> maps) 
{
    bool isLeverOpen = false;
    pair<int, int> start;
    pair<int, int> lever;
    pair<int, int> 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 };
            }
            else if (maps[i][j] == 'L')
            {
                lever = { i, j };
            }
            else if (maps[i][j] == 'E')
            {
                exit = { i, j };
            }
        }
    }

    int leverTime = bfs(maps, start, lever);
    if (leverTime == -1) return -1;

    int exitTime = bfs(maps, lever, exit);
    if (exitTime == -1) return -1;

    return leverTime + exitTime;
}

 

🔵 시간 복잡도 

미로 한 변의 길이를 N이라 할 때, bfs는 미로 전체를 탐색할 수 있으므로 최악의 경우 O(N^2) 시간 복잡도를 가진다.