[Programmers] 미로 탈출(LV.2)

풀이 소요시간 : 30분

탐색 완전기초 문제인데 맨날 백준만 풀다가 프로그래머스 환경이 낯선 탓에 시간의 절반정도를 잡아먹었다. 입출력도 없고 배열 입력이 vector 로 들어오는 것도 좀 당황스럽다. 실제 코딩테스트는 프로그래머스 환경과 유사하다던데 백준 컨벤션을 프로그래머스 식으로 바꾸기 연습도 좀 해야겠다.

시작 지점 - 레버 + 레버 - 출구 값을 구해주면 되는데, 이를 각각 구하고 하나라도 값을 구할 수 없다면 탈출을 실패한 것으로 적용한다.

전체 코드

#include <string>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;

int N, M;

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

int GOTO_OPEN = 0;
int GOTO_EXIT = 0;

int Open(int x, int y, vector<string> Map) {
    
    queue<pair<pair<int, int>, int>> Q;
    Q.push({{x, y}, 0});
    
    while(!Q.empty()) {
        
        int px = Q.front().first.first;
        int py = Q.front().first.second;
        int time = Q.front().second;
        Q.pop();
        
        if(Map[px][py] == 'L') {
            return time;
        }
        
        
        for(int i = 0; i < 4; i++) {
            int nx = px + dx[i];
            int ny = py + dy[i];
            
            if(nx < 0 || ny < 0 || nx >= N || ny >= M) continue; //범위 초과
            if(Visit[nx][ny] == 1) continue; //기존 방문
            if(Map[nx][ny] == 'X') continue; //벽 
            
            Visit[nx][ny] = 1;
            Q.push({{nx, ny}, time+1});
        }
        
    }
    return -1;
    //레버 접근 실패
}


int Exit(int x, int y, vector<string> Map) {
    
    queue<pair<pair<int, int>, int>> Q;
    Q.push({{x, y}, 0});
    
    while(!Q.empty()) {
        
        int px = Q.front().first.first;
        int py = Q.front().first.second;
        int time = Q.front().second;
        Q.pop();
        
        if(Map[px][py] == 'E') {
            return time;
        }
        
        
        for(int i = 0; i < 4; i++) {
            int nx = px + dx[i];
            int ny = py + dy[i];
            
            if(nx < 0 || ny < 0 || nx >= N || ny >= M) continue; //범위 초과
            if(Visit[nx][ny] == 1) continue; //기존 방문
            if(Map[nx][ny] == 'X') continue; //벽 
            
            Visit[nx][ny] = 1;
            Q.push({{nx, ny}, time+1});
        }
        
    }
    return -1;
    //탈출 실패
    
}


int solution(vector<string> maps) {
    
    N = maps.size();        //세로
    M = maps[0].length();   //가로
    
    for(int i = 0; i < N; i++) {             
        for(int j = 0; j < M; j++) {     
            if(maps[i][j] == 'S') {
                Visit[i][j] = 1;
                GOTO_OPEN = Open(i, j, maps);
            }
        }
    }
    
    memset(Visit, 0, sizeof(Visit));
    
    for(int i = 0; i < N; i++) {             
        for(int j = 0; j < M; j++) {     
            if(maps[i][j] == 'L') {
                Visit[i][j] = 1;
                GOTO_EXIT = Exit(i, j, maps);
            }
        }
    }
    
    if(GOTO_OPEN == -1 || GOTO_EXIT == -1) return -1;
    else return GOTO_OPEN + GOTO_EXIT;
}