프로그래머스[Programmers] - 미로 탈출(C++)[LV2]

문제

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

프로그래머스

---

🔎문제 해석

출발점에서 레버를 당겨서 탈출점까지의 최소 경로를 구하는 문제입니다.
BFS 알고리즘을 사용해서 쉽게 풀 수 있습니다.

 

문제는 굉장히 간단합니다..(저는 너무 복잡하게 생각해서 오래 걸렸습니다ㅜㅜ)

 

문제를 보면 출발정메서 레버로 있는 칸으로 이동하고, 레버를 당긴 후, 탈출점으로 이동하라고 나와 있습니다.

 

이 문제는 반드시 탈출을 하기 위해서는 레버를 당겨야 합니다.

만약 출발점에서 레버로 가는 경로가 없다면, 해당 미로는 탈출이 불가능한 미로입니다.

 

반대로 출발점에서 레버로 가는 경로를 구했는데, 레버에서 탈출점까지 이동이 불가능하다면, 탈출이 불가능한 미로입니다.

따라서 우리는 BFS를 두번 사용해야 합니다.

 

첫 번째는 출발점->레버의 경로를 구하는 BFS
두 번째는 레버 -> 탈출점  경로를 구하는 BFS

---

💻전체 코드

#include <iostream>
#include <string>
#include <vector>
#include <queue>
using namespace std;
int result=-1,Row,Col;
vector<vector<int>>visit;
vector<pair<int,int>>loc;
int dir[4][2]={ {1,0},{-1,0},{0,1},{0,-1}};
void init(vector<string>maps){
    for(int i=0; i<maps.size();i++){
        for(int j=0; j<maps[i].size();j++){
            if(maps[i][j]=='S')
             loc[0].first=i,loc[0].second=j;
            else if(maps[i][j]=='E')
                loc[1].first=i,loc[1].second=j;
            else if(maps[i][j]=='L')
                loc[2].first=i, loc[2].second=j;
        }
    }
}
int bfs(vector<string>maps, int s, int e){
    visit.assign(Row,vector<int>(Col,0)); //초기화
    queue<pair<int,int>> q; 
    q.push(make_pair(loc[s].first,loc[s].second)); //출발점을 넣기.
    while(!q.empty()){
        auto now = q.front();
        if(now.first==loc[e].first && now.second ==loc[e].second)
            return visit[now.first][now.second];
        q.pop();
        for(int i=0; i<4; i++){
            int tempr = now.first+dir[i][0];
            int tempc = now.second+dir[i][1];
            if(tempr<0 || tempc <0 || tempr>=Row || tempc>=Col|| maps[tempr][tempc]=='X'){
                continue; //적절하지 못한 이동 시 넘김.
            } 
            if(visit[tempr][tempc]!=0){ //처음 방문이 아니라면
                continue;
            }
            visit[tempr][tempc]=visit[now.first][now.second]+1;
            q.push(make_pair(tempr,tempc));
        }
    }
    return -1;
}
int solution(vector<string> maps) {
    int answer = 0,Row=maps.size(),Col=maps[0].size();
    loc.resize(3);
    init(maps); //출발지,탈출지,레버 위치 넣기
    answer = bfs(maps,0,2); //출발점에서 레버까지 최소경로 구하기.
    if(answer==-1) //만약 경로가 없다면 -1을 리턴
        return answer;
    else{ //경로가 있다면 이제 레베에서 탈출구 까지 경로를 구하기.
        int a =bfs(maps,2,1);  
        if(a==-1) //만약 경로가 없다면 -1을 리턴
            return a;
        else //경로가 있다면 두 경로를 합해주자.
            return answer+a;        
    }
}

자세한 코드는 주석을 읽어보시면 충분히 이해하실 수 있을 거라 생각합니다.

 

---

😀느낀 점

• 시간을 재고 풀어봤는데, 시간이 너무 오래 걸려서 시간을 단축하는 연습을 좀 해야 할 거 같습니다..
  • 문제를 이해하는데, 너무 시간이 오래 걸리는 거 같아서 , 문제를 읽는데 집중하고, 그에 따른 알고리즘도 바로바로 떠올리면 좋을 거 같습니다.
• 항상 BFS문제를 풀 때, 방문처리와 도착지점에 대한 종료조건을 어디다 걸어야 할지 헷갈립니다.
  • 이제부터는 일관성 있게 풀어야겠습니다.
•  프로그래머스는 굉장히 코딩하기 불편합니다.
  • 하지만 코딩테스트는 모두 여기를 사용하기 때문에, 적응해야겠지요.