프로그래머스 (C/C++) 159993 : 미로 탈출

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

프로그래머스

 

---

풀이

bfs를 사용하여 길을 찾았다.

최단 거리를 찾는 문제이므로 다음에 가려고 하는 곳이 이미 지나쳤던 곳이라면 갈 필요가 없음 -> visited 배열로 확인

다음 탐색할 곳은 큐에 담았고 Q({ {next_x, next_y} , now_cnt }) 의 형식을 사용했다. 

 

S, E는 정해지지 않았으므로 한 번은 배열을 뒤져야 한다. 그래서 이 때 vector 형식을 2차원 배열로 바꿔주었다.

이 때 (출발지점~레버), (레버~도착지점)으로 나눠 2번 계산했다. 

 

나눠서 계산한 이유

- 만약 (출발지점~레버)까지의 길이 없다면 (레버~도착지점) 탐색할 필요 X

- 레버에 도착한다면, (출발지점~레버) 동안 탐색한 곳을 (레버~도착지점)을 탐색할 때도 거쳐야 함
   -> 이 때 visited 배열을 초기화 해줘야 함 (처음엔 이를 위해 visited 배열을 따로 쓰지 않았고, 시간 초과가 발생)

의 이유로 탐색 과정을 함수로 따로 빼서 나눴다.

---

코드

#include <string>
#include <vector>
#include <queue>
#include <unordered_map>
#define X -100
#define S -1
#define L -2
#define E -3
using namespace std;

int M[100][100]={0,};
auto Bfs(int sx, int sy, int Find, int row, int col){   
    int m[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
    bool visited[100][100] = {false,};
    
    queue< pair< pair<int,int>, int > > Q;
    Q.push({{sx, sy}, 0});
    visited[sx][sy] = true;
    
    while(!Q.empty()){
        int x = Q.front().first.first, y = Q.front().first.second, cnt = Q.front().second;
        Q.pop();
        
        for(int i=0;i<4;i++){
            int nx = x + m[i][0], ny = y + m[i][1];
            if(nx < 0 || row <= nx || ny < 0 || col <= ny || M[nx][ny] == X || visited[nx][ny]) continue;

            if(M[nx][ny] == Find) return cnt+1;                
            else{
                Q.push({{nx, ny}, cnt+1});
                visited[nx][ny] = true;
            }
        }        
    }
    return -1;
}

int solution(vector<string> maps) {
    int row = maps.size(), col = maps[0].size();
    int a1, a2;
    unordered_map <char, int> val = {{'X', -100}, {'S', 0}, {'L', -2}, {'E', -3}};

    int sx, sy, lx, ly;
    
    // maps to M
    for(int i = 0; i < row; i++){
        for(int j = 0; j < col; j++){
            M[i][j] = val[maps[i][j]];
            if(maps[i][j] == 'S') sx=i, sy=j;
            else if(maps[i][j] == 'L') lx=i, ly=j;
        }
    }
    
    // find lever
    a1 = Bfs(sx, sy, L, row, col);
    if(a1 == -1) return -1;
    
    // find exit
    a2 = Bfs(lx, ly, E, row, col);
    if(a2 == -1) return -1;
    return a1+a2;
}