프로그래머스 2023.09.03 (2Lv 미로 탈출)

프로그래머스

문제

---

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

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

제한사항
  ◈ 5 ≤ maps의 길이 ≤ 100
        ◈ 5 ≤ maps[i]의 길이 ≤ 100
        ◈ maps[i]는 다음 5개의 문자들로만 이루어져 있습니다.
            ◈ S : 시작 지점
            ◈ E : 출구
            ◈ L : 레버
            ◈ O : 통로
            ◈ X : 벽
        ◈ 시작 지점과 출구, 레버는 항상 다른 곳에 존재하며 한 개씩만 존재합니다.
        ◈ 출구는 레버가 당겨지지 않아도 지나갈 수 있으며, 모든 통로, 출구, 레버, 시작점은 여러 번 지나갈 수 있습니다.

입출력 예

maps	result
["SOOOL","XXXXO","OOOOO","OXXXX","OOOOE"]	16
["LOOXS","OOOOX","OOOOO","OOOOO","EOOOO"]	-1

입출력 설명 예는 해당 프로그래머스 홈페이지를 참고해주세요.

코딩

---

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

using namespace std;

// 너비 우선 탐색을 마치고, 결과를 반환해주기 위한 구조체
struct tBFS_Info
{
    int iCost;
    int ix;
    int iy;
    bool bFind;
};

// 방문 처리 뿐 아니라 비용도 기록해주어야 하기 때문에 하나의 vector로 방문 처리와 비용 계산을 같이하기 위한 구조체
struct tVisit_Info
{
    bool    bVisit = false;
    int     iCost = 0;
};

// 방문 벡터를 초기화 해주는 함수
void VisitClear(vector<vector<tVisit_Info>>& _vecVisit)
{
    for (size_t i = 0; i < _vecVisit.size(); ++i)
    {
        for (size_t j = 0; j < _vecVisit[i].size(); ++j)
        {
            _vecVisit[i][j].bVisit = false;
            _vecVisit[i][j].iCost = 0;
        }
    }
}

// bfs에서 사용되는 queue를 초기화(비워주는) 해주는 함수
void queueClear(queue<pair<int, int>>& _queue)
{
    while (!_queue.empty())
    {
        _queue.pop();
    }
}

// 너비 우선 탐색 함수
tBFS_Info bfs(vector<string>& _map, queue<pair<int, int>>& _queue, vector<vector<tVisit_Info>>& _vecVisit, char _cTarget)
{
    int arrx[4] = { 1,0,-1,0 };
    int arry[4] = { 0,1,0,-1 };
    tBFS_Info NewBFSInfo = {};
    NewBFSInfo.bFind = false;

    while (!_queue.empty())
    {
        // 이번 탐색할 인덱스 꺼내기
        int iY = _queue.front().first;
        int iX = _queue.front().second;

        _queue.pop();

        // 이번 검사하는 인덱스가 목표를 찾으면
        if (_map[iY][iX] == _cTarget)
        {
            NewBFSInfo.iCost = _vecVisit[iY][iX].iCost;
            NewBFSInfo.ix = iX;
            NewBFSInfo.iy = iY;
            NewBFSInfo.bFind = true;

            return NewBFSInfo;
        }
        // 찾지 못했다면,
        else
        {
            for (size_t i = 0; i < 4; ++i)
            {
                int iNY = iY + arry[i];
                int iNX = iX + arrx[i];

                // map 범위 내의 idx인지 체크
                if ((iNX >= 0 && iNX < _map[0].length())
                    && (iNY >= 0 && iNY < _map.size()))
                {
                    // 인접 인덱스들 중 방문했던 적이 없고, 벽이 아닐 경우에만
                    if (_vecVisit[iNY][iNX].bVisit == false && _map[iNY][iNX] != 'X')
                    {
                        // 방문 처리 후 코스트를 증가시키고 queue에 넣어준다.
                        _vecVisit[iNY][iNX].bVisit = true;
                        _vecVisit[iNY][iNX].iCost = _vecVisit[iY][iX].iCost + 1;
                        _queue.push(make_pair(iNY, iNX));
                    }
                }
            }
        }
    }

    return NewBFSInfo;
}

int solution(vector<string> maps) {
    int answer = 0;

    bool bLever = false;
    queue<pair<int, int>> queue = {};

    // 방문 처리할때 필요한 방문 벡터 만들기
    vector<vector<tVisit_Info>> vecVisit(maps.size());
    for (int i = 0; i < maps.size(); ++i)
    {
        tVisit_Info Info = {};
        vecVisit[i].resize(maps[i].length(), Info);
    }

    // 시작 지점 찾기
    for (size_t i = 0; i < maps.size(); ++i)
    {
        for (size_t j = 0; j < maps[i].length(); ++j)
        {
            if (maps[i][j] == 'S')
            {
                queue.push(make_pair(i, j));
                break;
            }
        }
    }

    // 너비 우선 탐색 진행 (레버 찾기 먼저 진행)
    tBFS_Info tBFS_Find;
    tBFS_Find = bfs(maps, queue, vecVisit, 'L');

    // 만약 레버를 찾지 못했다는 것은 탈출 불가능하다는 뜻이므로 -1을 반환
    if (tBFS_Find.bFind == false)
    {
        return -1;
    }
    else
    {
        answer += tBFS_Find.iCost;
    }

    //만약 레버를 작동 시켰다면, 레버에서 탈출구 까지의 최단 경로 구하기 진행
    VisitClear(vecVisit);
    queueClear(queue);
    queue.push(make_pair(tBFS_Find.iy, tBFS_Find.ix));
    tBFS_Find = bfs(maps, queue, vecVisit, 'E');

    if (tBFS_Find.bFind == false)
    {
        return -1;
    }
    else
    {
        answer += tBFS_Find.iCost;
    }

    return answer;
}

해당 문제는 길 찾기 알고리즘으로 푸는 문제이다.

처음에는 A* 알고리즘이나 Dijkstra 알고리즘으로 풀려했지만, 잘 생각해보면 각 칸간의 이동 시간은 1로 동일하기 때문에 이런 길찾기 알고리즘을 사용하지 않아도 BFS(너비 우선 탐색)으로 충분히 풀 수 있는 문제라 판단해 BFS를 이용해 풀어주었다.

 

처음에는 노드를 만들고 노드의 주소끼리 연결해 미로 맵을 만들어 탐색을 해주려 했다. 하지만, 이미 인자로 맵을 구성해서 주기 때문에 노드를 만들고 주소끼리 연결해주는 작업은 불필요하다고 생각했다. (주로 길찾기 알고리즘을 짤때, 혹은 내가 포토폴리오를 진행하며 게임을 만들었을 때, 노드 단위로 만들었기 때문에 노드 구성을 짤 생각을 처음에는 했던 것 같다.)

 

이 문제를 BFS로 풀기 위해 필요한 것들은 방문 처리를 해줄 별도의 vector와 인덱스를 꺼내 검사해줄 queue가 필요했다.

또, 최단 거리를 찾는 문제이기 때문에 iCost를 만들어 비용을 계산해줄 필요가 있었다.

 

이후 첫 시작지점인 'S'를 찾아 queue에 넣어주고, 방문 처리 vector인 vecVisit을 초기화 해주었다.

이를 기점으로 BFS 탐색을 해줄 bfs() 함수를 만들어주고, 함수 내에서는 이번에 검사하는 인덱스에 목표('L' 혹은 'E')가 있는지, 벽이 있는지를 확인해가며, 다음 칸으로 이동할 수 있고 없고를 비교해 수행해주었다.

bfs 도중 이번 검사하는 인덱스의 인접 인덱스에는 기존 인덱스 cost에 1을 더한 값을 cost로 지정해 비용을 계산해 나가 주었다. (모든 인덱스간 비용은 1이기 때문에 따로 비용을 검사해 적은 비용이 드는 곳을 판별하지 않아도 되는 문제였다.)

 

bfs 탐색을 통해 문제를 잘 풀었지만, 코드를 좀 더 간결하게 짤 수 있을 것 같은데, 푸는데에만 급급해 조금 난잡하게 된 점이 불만족스러운 것 같다.

길찾기 알고리즘 문제를 더 풀면서 바로바로 풀어도 코드가 좀더 깔끔하게 나오도록 연습을 더 해야할 것 같다.

실행 결과

---