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

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

 

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

프로그래머스

---

 

해결 전략

 

너비우선탐색 BFS

 

 

레버(L)를 먼저 찾은 후에 탈출구(E)를 찾아야 한다.

1. 레버(L)를 찾는 BFS 수행
   • 주의할 점: 이 때 탈출구를 지나칠 수 있다. 탈출구를 지나도 밖에 나가 끝나지 않고 그냥 지나친 시간만 카운팅한다.
2. 방문 체크 초기화
   • fill(ch.begin(), ch.end(), vector<int>(c, 0));
3. 탈출구(E)를 찾는 BFS 수행
   • 주의할 점: 이 때 시작점(S)을 지나칠 수 있다. 이 경우에 수도 체크해야 한다.

 

 

※ 참고사항: 2차원 배열의 fill 초기화

fill(ch.begin(), ch.end(), vector<int>(c, 0));

---

 

정답 코드

 

#include <iostream>
#include <string>
#include <vector>
#include <queue>
using namespace std;
 
int dirY[4] = { -1, 0, 1, 0 };
int dirX[4] = { 0, -1, 0, 1 };
 
int answer = -1; // 미로를 빠져나가는데 걸리는 최소 시간. 초기값은 -1로 설정
 
int solution(vector<string> maps) {
 
    int r = maps.size();
    int c = maps[0].size();
 
    queue<pair<int, int>> Q;       // 레버를 찾을때까지 탐색할 좌표를 저장할 큐
    queue<pair<int, int>> secondQ; // 레버를 작동시킨 후 탐색할 좌표를 저장할 큐
    vector<vector<int>> ch(r, vector<int>(c, 0)); // 방문한 좌표를 체크할 2차원 벡터
 
    for (int y = 0; y < r; y++) {
        for (int x = 0; x < c; x++) {
            if (maps[y][x] == 'S') { // 시작 지점의 좌표를 큐에 넣음
                Q.push({ y, x });
            }
        }
    }
 
    int cnt = 0;         // 레버를 작동시킨 후의 이동 시간을 저장할 변수
    bool bLever = false; // 레버를 작동시켰는지 여부를 저장할 변수
    while (!Q.empty()){
        int y = Q.front().first;
        int x = Q.front().second;
        Q.pop();
 
        for (int i = 0; i < 4; i++) {
            int ny = y + dirY[i];
            int nx = x + dirX[i];
 
            if (ny < 0 || r <= ny || nx < 0 || c <= nx || maps[ny][nx] == 'X') continue;
 
            if (maps[ny][nx] == 'O' && ch[ny][nx] == 0){ // 빈 칸('O')이고 방문하지 않았다면
                Q.push({ ny, nx }); // 큐에 좌표를 넣고
                ch[ny][nx] = ch[y][x] + 1; // 이동 시간를 증가
            }
            else if (maps[ny][nx] == 'E' && ch[ny][nx] == 0) { // 출구('E')이고 방문하지 않았다면
                Q.push({ ny, nx });
                ch[ny][nx] = ch[y][x] + 1;
            }
            else if (maps[ny][nx] == 'L' && ch[ny][nx] == 0) { // 레버('L')이고 방문하지 않았다면
                secondQ.push({ ny, nx }); // 레버 작동 후의 좌표를 저장할 큐에 좌표를 넣고
                ch[ny][nx] = ch[y][x] + 1;
                cnt = ch[ny][nx]; // 레버를 작동시킨 좌표의 이동 시간을 저장
                //cout << "cnt = " << cnt << "\n";
                bLever = true; // 레버 작동 표시
                break;
            }
        }
 
        if (bLever) break;
    }
 
    if (bLever == false) return answer; // 레버를 찾지 못하면 -1을 반환
 
    fill(ch.begin(), ch.end(), vector<int>(c, 0)); // 방문 체크 벡터를 초기화
    ch[secondQ.front().first][secondQ.front().second] = cnt; // 레버를 작동시킨 좌표의 이동 시간을 저장
 
    bool bArrived = false; // 종료 지점에 도착했는지 여부를 저장할 변수
    while (!secondQ.empty()) { // 레버를 작동시킨 후의 탐색
        int y = secondQ.front().first;
        int x = secondQ.front().second;
        secondQ.pop();
 
        for (int i = 0; i < 4; i++) {
            int ny = y + dirY[i];
            int nx = x + dirX[i];
 
            if (ny < 0 || r <= ny || nx < 0 || c <= nx || maps[ny][nx] == 'X') continue;
 
            if (maps[ny][nx] == 'O' && ch[ny][nx] == 0) { // 빈 칸('O')이고 방문하지 않았다면
                secondQ.push({ ny, nx });
                ch[ny][nx] = ch[y][x] + 1;
            }
            else if (maps[ny][nx] == 'S' && ch[ny][nx] == 0) { // 시작 지점('S')이고 방문하지 않았다면
                secondQ.push({ ny, nx });
                ch[ny][nx] = ch[y][x] + 1;
            }
            else if (maps[ny][nx] == 'E' && ch[ny][nx] == 0) { // 출구('E')이고 방문하지 않았다면
                secondQ.push({ ny, nx });
                ch[ny][nx] = ch[y][x] + 1;
                answer = ch[ny][nx]; // 최종 이동 시간을 answer에 저장
                bArrived = true; // 도착 표시
                break;
            }
        }
 
        if (bArrived) break;
    }
 
 
    return answer;
}
 
int main() {
    vector<string> testcase1 = { "SOOOL","XXXXO","OOOOO","OXXXX","OOOOE" };
    //vector<string> testcase2 = { "LOOXS","OOOOX","OOOOO","OOOOO","EOOOO" };
 
    cout << solution(testcase1) << "\n";
    //cout << solution(testcase2) << "\n";
 
    return 0;
}

 

 

---