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

프로그래머스

 

예시 1의 이미지

 

• 출발점에서 레버까지 bfs 수행
• 레버에서 출구까지 bfs 수행

> 총 2번 bfs를 수행하면 되는 문제

 

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

using namespace std;

int dirX[4] = {0, 0, -1, 1};
int dirY[4] = {1, -1, 0, 0};

int bfs(vector<string> maps, queue<pair<int, int>> q, int n, int m, char target) {
    // 방문 배열
    int dist[n][m];
    // -1로 초기화
    memset(dist, -1, sizeof(dist));
    
    // 시작 지점의 방문 배열 값은 0
    dist[q.front().first][q.front().second] = 0;
    
    while(!q.empty()) {
        pair<int, int> cur = q.front();
        q.pop();
        
        for(int i = 0; i < 4; i++) {
            int nx = cur.first + dirX[i];
            int ny = cur.second + dirY[i];
            
            if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            
            if(maps[nx][ny] == 'X' || dist[nx][ny] != -1) continue;
            
            // target을 만나면 해당 target까지 이동한 횟수 리턴
            if(maps[nx][ny] == target) return dist[cur.first][cur.second] + 1;
            
            // 아니라면 방문 횟수를 저장하고 현재 위치 갱신
            dist[nx][ny] = dist[cur.first][cur.second] + 1;
            
            q.push({nx, ny});
        }
    }
    
    return -1;
}

int solution(vector<string> maps) {
    int answer = 0;
    int n = maps.size();
    int m = maps[0].size();
    
    // 각각 레버, 출구로 갈 때 쓸 큐
    queue<pair<int, int>> toLever, toExit;
    
    // 각각 출발점의 좌표와 레버의 좌표 저장
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(maps[i][j] == 'S') toLever.push({i, j});
            else if(maps[i][j] == 'L') toExit.push({i, j});
        }
    }
    
    int tmp;
    
    // 레버로
    answer = bfs(maps, toLever, n, m, 'L');
    
    // 출구로
    if(answer == -1) return -1;
    else tmp = bfs(maps, toExit, n, m, 'E');
    
    if(tmp == -1) return -1;
    else answer += tmp;
    
    return answer;
}