[Lv 2] 미로 탈출

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

프로그래머스

 

이 문제는 bfs를 이용한 길 찾기를 통해 해결할 수 있다.

문제에서 모든 통로와 출구, 레버, 시작점을 여러번 지나갈 수 있는 조건은 문제 해결 시 많은 어려움을 가져다 주었다.

 

이 조건은 레버를 찾기 전까지 성립하지 않는 것을 알게 되었다.

그 이유는 이동 횟수가 최소가 되기 위해선 bfs나 dfs를 사용해야한다. 하지만 레버를 찾기 전에 같은 위치를 여러번 이동할 수 있다면, 최소 이동을 할 수 없다.

따라서 레버를 찾기 위한 bfs와 레버를 찾고 난 후 출구를 찾기 위한 bfs를 호출하면 문제를 해결할 수 있다.

 

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

using namespace std;
int dy[] = {-1, 1, 0, 0};
int dx[] = {0, 0, -1, 1};
int y, x;
int answer;
bool visited[101][101];

void bfs2(int my, int mx, vector<string> maps, int& answer){
    memset(visited, false, sizeof(visited));

    queue<pair<pair<int, int>, int>> q;
    q.push({{my, mx}, answer});
    answer = 987654321;
    visited[my][mx] = true;
    while(!q.empty()){
        int qy = q.front().first.first;
        int qx = q.front().first.second;
        int counter = q.front().second;
        q.pop();
        if(maps[qy][qx] == 'E'){
            answer = min(answer, counter);
            break;
        }
            
        for(int i = 0;i<4;i++){
            int uy = qy + dy[i];
            int ux = qx + dx[i];
            
            if(uy < 0 || uy >= y || ux < 0 || ux >= x || maps[uy][ux]=='X')
                continue;
            if(!visited[uy][ux]){
                visited[uy][ux] = true;
                q.push({{uy, ux}, counter+1});
            }
        }
    }
}

void bfs1(int my, int mx, vector<string> maps, int& answer){
    int exitX = 0, exitY = 0;
    queue<pair<pair<int, int>, int>> q;
    q.push({{my, mx}, 0});
    visited[my][mx] = true;
    while(!q.empty()){
        int qy = q.front().first.first;
        int qx = q.front().first.second;
        int counter = q.front().second;
        q.pop();
        if(maps[qy][qx] == 'L'){
            answer = min(answer, counter);
            exitX = qx;
            exitY = qy;
            break;
        }
            
        for(int i = 0;i<4;i++){
            int uy = qy + dy[i];
            int ux = qx + dx[i];
            
            if(uy < 0 || uy >= y || ux < 0 || ux >= x || maps[uy][ux]=='X')
                continue;
                
            if(!visited[uy][ux]){
                visited[uy][ux] = true;
                q.push({{uy, ux}, counter+1});
            }
        }
    }
    if(answer==987654321)
        return;

    bfs2(exitY, exitX, maps, answer);
}

int solution(vector<string> maps) {
    int answer = 987654321;
    y = maps.size();
    x = maps[0].size();
    
    for(int i = 0;i<y; i++){
        for(int j = 0;j<x;j++){
            if(maps[i][j]=='S')
                bfs1(i, j, maps, answer);
        }
    }
    if(answer == 987654321) 
        return -1;
    return answer;
}