[C++] 미로 탈출 (프로그래머스 LEVEL 2)

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

프로그래머스

---

문제풀이

시작점에서 레버를 찍고, 레버에서 도착지점을 찍는 최단 거리를 찾는 문제다.

bfs를 두번 돌리면 되겠다고 생각했다.

두번 돌려야 하므로 함수로 따로 빼서 작성해 주었다.

주의할 점은, 목표 지점에 도달하지 못하는 경우를 처리해 주어야 한다. 함수에서 목표지점에 도달하지 못한경우 1(true), 도달 한경우 0(false)를 리턴해 주도록 했다.

 

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

using namespace std;

int arr[100][100];
int answer;

bool bfs(int& n, int& m, pair<int, int>& start, pair<int, int>& end) {
    int visited[n][m];
    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
            visited[i][j] = 0;
        }
    }
    queue<pair<int, pair<int, int>>> q;
    q.push({0, {start.first, start.second}});
    visited[start.first][start.second] = 1;
    
    int ret = 1;
    while(!q.empty()) {
        int r = q.front().second.first;
        int c = q.front().second.second;
        int v = q.front().first;
        
        // cout << r << " " << c << " " << v << endl;
        
        q.pop();
        
        if(r == end.first && c == end.second) {
            // cout << v << endl;
            answer += v;
            return 0;
        }
        
        int a[] = {0, 0, 1, -1};
        int b[] = {1, -1, 0, 0};
        for(int i=0; i<4; i++) {
            int dr = r + a[i];
            int dc = c + b[i];
            
            if(dr>=0 && dr<n && dc>=0 && dc<m && visited[dr][dc] == 0 && arr[dr][dc] != 'X') {
                q.push({v+1, {dr, dc}});
                visited[dr][dc] = 1;
            }
        }
    }
    return ret;
}

int solution(vector<string> maps) {    
    pair<int, int> start;
    pair<int, int> lever;
    pair<int, int> end;
    for(int i=0; i<maps.size(); i++) {
        for(int j=0; j<maps[i].size(); j++) {
            if(maps[i][j] == 'S') start = {i, j};
            if(maps[i][j] == 'L') lever = {i, j};
            if(maps[i][j] == 'E') end = {i, j};
            arr[i][j] = maps[i][j];
        }
    }
    int n = maps.size();
    int m = maps[0].size();
    if(bfs(n, m, start, lever)) return -1;
    if(bfs(n, m, lever, end)) return -1;
    return answer;
}