코딩테스트 : 미로 탈출

해당 문제는 미로에서 시작 지점부터 레버를 당기고 출구까지 도달하는 최소 시간을 구하는 문제이다.

 

최단 거리의 거리를 구하는 문제이기 때문에 DFS가 아닌 BFS를 사용하여 효율성을 높여준다. 또한 레버까지 가는 길과 출구 까지 가는 길은 겹치는 것이 가능하기 때문에 각각 최단거리를 구해서 더해야한다.

 

BFS에 대한 자세한 설명은 아래 링크에 정리해두었다.

BFS(Breadth-First-Search) 넓이 우선 탐색

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

using namespace std;

vector<vector<char>> map; // 미로 정보를 저장할 2차원 벡터

// BFS를 사용하여 특정 지점(target)까지의 최단 거리를 찾는 함수
int findMaze(char target, pair<int, int>& Pos)
{
    // 이동 방향 (상, 하, 좌, 우)
    vector<pair<int, int>> direction = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
    
    // 방문 여부를 저장할 2차원 벡터
    vector<vector<bool>> visited(map.size(), vector<bool>(map[0].size(), false));
    // 큐: {{x, y}, step} (x, y 좌표와 이동 횟수)
    queue<pair<pair<int, int>, int>> q;
    q.push({Pos, 0}); // 시작 위치와 이동 횟수 0을 큐에 삽입
    visited[Pos.second][Pos.first] = true; // 시작 위치 방문 처리
    
    // 큐가 빌 때까지 반복
    while(!q.empty())
    {
        pair<pair<int, int>, int> temp = q.front(); // 큐의 맨 앞 요소 가져오기
        q.pop(); // 큐에서 제거
        
        // 4가지 방향으로 이동
        for(int i = 0; i < 4; i++)
        {
            int nextX = temp.first.first + direction[i].first; // 다음 x 좌표
            int nextY = temp.first.second + direction[i].second; // 다음 y 좌표
            
            // 미로 범위를 벗어나는 경우 무시
            if(!(nextX >= 0 && nextY >= 0 && nextX < map[0].size() && nextY < map.size()))
                continue;

            // 벽인 경우 무시
            if(map[nextY][nextX] == 'X')
                continue;

            // 이미 방문한 위치인 경우 무시
            if(visited[nextY][nextX] == true)
                continue;

            // 목표 지점을 찾은 경우
            if(map[nextY][nextX] == target)
            {
                Pos = make_pair(nextX, nextY); // 현재 위치를 목표 지점으로 갱신
                return temp.second + 1; // 이동 횟수 반환
            }

            // 큐에 다음 위치 정보 삽입
            q.push(make_pair(make_pair(nextX, nextY), temp.second + 1));
            visited[nextY][nextX] = true; // 방문 처리
            
        }
    }
    
    return -1; // 목표 지점에 도달할 수 없는 경우 -1 반환
}

int solution(vector<string> maps) {
    int answer = 0; // 총 이동 횟수를 저장할 변수 초기화
    
    // 미로 정보를 2차원 벡터에 저장
    map = vector<vector<char>>(maps.size(), vector<char>(maps[0].size()));
    pair<int, int> Pos; // 시작 위치를 저장할 변수

    // 미로 정보 초기화 및 시작 위치 찾기
    for(int i = 0; i < maps.size(); i++)
    {
        for(int j = 0; j < maps[0].size(); j++)
        {
            map[i][j] = maps[i][j]; // 미로 정보 저장
            if(maps[i][j] == 'S')
                Pos = make_pair(j, i); // 시작 위치 저장
        }
    }
    
    // 시작 위치에서 레버까지의 최단 거리
    int resultL = findMaze('L', Pos);
    if(resultL == -1)
        return -1; // 레버에 도달할 수 없는 경우 -1 반환
    
    // 레버에서 출구까지의 최단 거리
    int resultE = findMaze('E', Pos);
    if(resultE == -1)
        return -1; // 출구에 도달할 수 없는 경우 -1 반환
    
    // 총 이동 횟수 반환
    return resultL + resultE;
}

목표 지점을 매개변수로 넘겨주므로써 레버와 출구까지의 최단거리를 각각 구분해서 구할 수 있게 구현하였다.

 

maps ["SXXXL", "OXXOX", "OXXOX", "OXXOX", "OXXOE"]
return -1

maps ["SLOOO", "OOOOO", "OOOOO", "OOOOO", "OOEOO"]
return 6

maps ["SXXOX", "OXXOX", "OXXOX", "OXXOX", "OXXLE"]
return -1

maps ["SXXXX", "OXXXX", "OXLXX", "OXXXX", "OOEOO"]
return -1

maps ["SOOOO", "OXXXX", "OXLXO", "OXXXX", "OOEOO"]
return -1

maps ["SOOOO", "OXLXO", "OXXXX", "OOOOO", "OOEOO"]
return 12