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

문제 링크

미로 탈출

 

풀이

BFS를 이용하는 문제

1. 미로를 만들면서 출발 지점인 stt와 도착 지점인 end를 만들어준다.
2. BFS를 돌리는데 시간이 갱신될 time을 3차원 배열로 만들어준다. 원래 2차원 배열의 BFS는 방문한 지점을 다시 방문하지 않는데, 이 문제는 레버를 누르고 도착 지점으로 가야하기 때문에 왔던 길을 다시 방문할 수도 있다.
   1. 구조체 Cell을 정의한다. 위치가 담길 y와 x, 레버가 당겨졌었는지 확인할 flag로 구성되어 있다.
   2. 도착지점부터 q에 넣고 상하좌우를 탐색한다.
   3. 범위 밖이거나 벽이거나 방문 했었다면 continue, 레버라면 해당 지점에서 차원이 옮겨지게 된다.
   4. time을 갱신하고 q에 새로운 위치를 넣어준다.
3. time[end.first][end.second][1]을 return하면 레버를 누른 도착 지점에서의 시간이 나온다.

 

코드

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

using namespace std;

int dy[4] = {-1,0,1,0};
int dx[4] = {0,1,0,-1};

struct Cell
{
    int y;
    int x;
    bool flag; // 레버를 당겼는지
};

int bfs(pair<int,int> stt, pair<int,int> end, vector<vector<char>> &arr)
{
    int row = arr.size(); int col = arr[0].size();
    int time[101][101][2];
    queue<Cell> q;

    for(int i=0;i<101;i++) // time 배열 초기화
    {
        for(int j=0;j<101;j++)
        {
            time[i][j][0] = -1;
            time[i][j][1] = -1;
        }
    }

    time[stt.first][stt.second][0] = 0;
    q.push({stt.first, stt.second, 0});

    while(!q.empty())
    {
        int ty = q.front().y;
        int tx = q.front().x;
        bool lf = q.front().flag; // lever flag
        q.pop();
        for(int i=0;i<4;i++)
        {
            int ny = ty+dy[i];
            int nx = tx+dx[i];
            if(ny<0 || ny>=row || nx<0 || nx>=col) continue; // 범위 밖이면
            if(arr[ny][nx] == 'X') continue; // 벽이면
            if(time[ny][nx][lf] != -1) continue; // 방문했었다면
            if(arr[ny][nx] == 'L')
            {
                time[ny][nx][lf] = time[ty][tx][lf]+1;
                time[ny][nx][1] = time[ty][tx][lf]+1;
                q.push({ny,nx,1});
            }
            else
            {
                time[ny][nx][lf] = time[ty][tx][lf]+1;
                q.push({ny,nx,lf});
            }
        }
    }
    return time[end.first][end.second][1];
}

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

    vector<vector<char>> arr(maps.size());
    pair<int,int> stt;
    pair<int,int> end;

    for(int i=0;i<maps.size();i++)
    {
        for(int j=0;j<maps[i].size();j++)
        {
            arr[i].push_back(maps[i][j]);
            if(maps[i][j] == 'S') stt = make_pair(i,j);
            else if(maps[i][j] == 'E') end = make_pair(i,j);
        }
    }

    answer = bfs(stt, end, arr);
    return answer;
}