[프로그래머스 Lv.2] 미로 탈출(bfs 응용)

문제 풀러 바로가기 >> 미로 탈출

🔗 문제

---

🤷‍♂️ 문제 조건

---

😒 내가 생각한 아이디어

---

😶‍🌫️ 문제를 통해 이해해보기

여러모로 문제에 트릭을 많이 심어놓은 것 같다. (너만 넘어갔어)
특히 문제 조건 중에 이 마지막 조건 때문에 헷갈렸다.

• 출구는 레버가 당겨지지 않아도 지나갈 수 있으며, 모든 통로, 출구, 레버, 시작점은 여러 번 지나갈 수 있습니다.

출구는 레버가 당겨지지 않아도 지나갈 수 있다고 해서, 그냥 레버의 존재와 상관없이 시작 좌표 ▶️ 출구로 bfs 한 번만 돌리면 되는 줄 알았다. 그리고 어김없이 나오는 에러...
그래서 그냥 처음 생각했던 대로

(시작 좌표 ▶️ 레버) + (레버 ▶️ 출구)
bfs 돌려서 최댓값 찾으면 된다.

---

⚒️ 뚝딱뚝딱 설계

---

🖥️ 정답 코드

---

#include <string>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int, int> pi;

int bfs(vector<string> &maps, pi start_node, pi end_node, int &row, int &col){
    const int dx[] = {1, -1, 0, 0}; //동 서 남 북
    const int dy[] = {0, 0, -1, 1}; 
    queue<pi> q; // 자료구조 큐 선언
    vector<vector<bool>> visited(row, vector<bool>(col, false)); //방문체크 좌표
    vector<vector<int>> dist(row, vector<int>(col, 0)); //거리 세어주는 좌표
    visited[start_node.first][start_node.second]= true; //방문 체크해주고
    q.push({start_node.first, start_node.second}); //자료구조 큐에 밀어넣기
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for(int i =0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx < 0 || ny < 0 || nx >= row || ny >= col) {
                continue;
            }
            if(visited[nx][ny] == true){
                continue;
            }
            if(maps[nx][ny]=='X') {
                continue;
            }
            visited[nx][ny] = true; //방문 처리 해주고
            q.push({nx, ny}); //큐에 밀어넣기 
            dist[nx][ny] = dist[x][y] + 1;
            if(nx == end_node.first && ny == end_node.second) {
                return dist[nx][ny];
            }
        }
    }
    if(visited[end_node.first][end_node.second]==false) {
        return -1;
    }
    
}
int solution(vector<string> maps) {
    int answer = 0;
    int row = maps.size(); // row = 가로 길이
    int col = maps[0].size();  // col = 세로 길이
    pi start;
    pi lever;
    pi end;
    for(int i =0; i < row; i++){
        for(int j = 0; j < col; j++){
           if(maps[i][j]== 'S'){ //start 좌표
               start = make_pair(i, j);
           } else if(maps[i][j]== 'L'){ //lever 좌표
               lever = make_pair(i, j);
           } else if(maps[i][j]== 'E'){ //end 좌표
               end = make_pair(i, j);
           }
        }
    }
    int ans1= bfs(maps, start, lever, row, col);
    int ans2= bfs(maps, lever, end, row, col);
    if(ans1 < 0 || ans2 < 0) {
        answer = -1;
    } else {
        answer = ans1+ans2;
    }
    return answer;
}