[ 프로그래머스 C++ ] 미로 탈출 lv2

< 해설 >

기본적이긴 하나.. 구현에 고민이 생기게 하는 BFS 문제였다. 보통의 BFS와는 다르게 탐색을 2번 해야하는 문제이기 때문. 그래서 시작 지점과 끝 지점을 입력했을 시 최단 거리를 리턴하는 함수를 만들어서 사용했다.

또한 2차원 배열을 2개를 두어 무엇을 찾는지 (레버를 찾는지 탈출구를 찾는지) 를 물어보고 각각의 다른 2차원 배열을 사용했다.

 

< 문제 >

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

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

입출력 예

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

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

 

 

< 풀이>

#include <string>
#include <vector>
#include <queue>
#include "string.h"

using namespace std;

int arr1[101][101];
int arr2[101][101];
int defense[4][2] = {{-1,0},{0,-1},{1,0},{0,1}};

int findRoad(const char& _SorL, pair<int, int> _index, pair<int, int> _start, int _mapSize1, int _mapsize2)
{
    int sec = -1;
    queue<pair<int, int>> q;
    q.push(_start);
    while (!q.empty())
    {
        pair<int, int> cur = q.front();
        q.pop();

        if (cur == _index)
        {
            if (_SorL == 'L')
                sec = arr1[cur.first][cur.second];
            else
                sec = arr2[cur.first][cur.second];

            break;
        }
        else
        {
            for (int i = 0; i < 4; i++)
            {
                int nextX = cur.first + defense[i][0];
                int nextY = cur.second + defense[i][1];

                if (nextX >= 0 && nextY >= 0 && nextX < _mapSize1
                    && nextY < _mapsize2)
                {
                    if (_SorL == 'L')
                    {
                        if (arr1[nextX][nextY] == 0)
                        {
                            arr1[nextX][nextY] = arr1[cur.first][cur.second] + 1;
                            q.push(make_pair(nextX, nextY));
                        }                        
                    }
                    else
                    {
                        if (arr2[nextX][nextY] == 0)
                        {
                            arr2[nextX][nextY] = arr2[cur.first][cur.second] + 1;
                            q.push(make_pair(nextX, nextY));
                        }
                    }
                }
            }
        }
    }
    return sec;
}

int solution(vector<string> maps) {
    int answer = -1;
    memset(arr1, -1, sizeof(arr1));
    memset(arr2, -1, sizeof(arr2));
    
    pair<int, int> start;
    pair<int, int> leber;
    pair<int, int> exit;
    
    for (int i = 0; i < maps.size(); i++)
    {
        for (int j = 0; j < maps[i].size(); j++)
        {
            if (maps[i][j] != 'X')
            {
                if (maps[i][j] == 'S')
                    start = make_pair(i, j);
                else if (maps[i][j] == 'E')
                    exit = make_pair(i, j);
                else if (maps[i][j] == 'L')
                    leber = make_pair(i, j);

                arr1[i][j] = 0;
                arr2[i][j] = 0;
            }
        }
    }
    
    int leberCount = findRoad('L', leber, start, maps.size(), maps[0].size());
    int exitCount = findRoad('E', exit, leber, maps.size(), maps[0].size());
    
    if(leberCount != -1 && exitCount != -1)
        answer = leberCount + exitCount;
    
    return answer;
}