[프로그래머스] Level 2. 미로 탈출

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

프로그래머스

 

해결 방법(실패)

BFS를 이용하여 최단 거리를 찾으려 했다. 

• S와 L, E 의 인덱스를 찾는다.
• S 에서 L 로 goSearch() , L에서 E로 goSerach() 를 수행하여 합을 리턴한다. 둘중 하나라도 -1이 나올 경우, 경로가 없다는 의미이므로 -1을 반환한다. goSearch() 는 아래와같이 동작한다.
  • 검사여부를 저장하는 visited와, 검사 대기줄인 queue를 생성한다. 시작점부터 queue에 넣고, 상,하,좌,우를 검사한다. 
  • 옆칸을 검사는 1) 맵 밖을 벗어나지 않고, 2) 해당 칸이 'X' 가 아니며, 즉 막혀있지 않으며, 3) 아직 검사가 진행되지 않은 칸(visited[i][j] == -1 ) 이어야만 검사를 진행한다.
  • 원하는 도착지에 도착했을 경우 dist를 리턴한다.

#include <string>
#include <vector>
#include <iostream>
#include <queue>
using namespace std;

int goSearch(vector<string>& maps, pair<int,int> start, pair<int,int> end){
    vector<vector<int>> visited(maps.size(), vector<int>(maps[0].size(),-1));
    queue<pair<int,int>> q;
    q.push(make_pair(start.first*1000 + start.second,0));
    
    while(!q.empty()){
        
        auto& crr = q.front();
        q.pop();
        int i  = crr.first /1000 ; int j = crr.first %1000; int dist = crr.second;    
        visited[i][j] = 1;
        
        if(i == end.first && j == end.second) return dist;
    
        if(i-1 >= 0 && maps[i-1][j] != 'X' && visited[i-1][j] == -1) q.push(make_pair((i-1)*1000 + j,dist+1));
        if(i+1 < maps.size() && maps[i+1][j] != 'X' && visited[i+1][j] ==-1) q.push(make_pair((i+1)*1000 + j, dist+1));
        if(j-1 >= 0 && maps[i][j-1] != 'X' && visited[i][j-1] ==-1) q.push(make_pair(i*1000 + j-1,dist+1));
        if(j+1 < maps[i].size() && maps[i][j+1] != 'X' && visited[i][j+1] ==-1)q.push(make_pair(i*1000 + j+1 , dist+1));  
        
    }
    
    return -1;
}

int solution(vector<string> maps) {
    pair<int,int> s, l , e;
   
    for(int i=0; i<maps.size(); i++){
        for(int j=0; j<maps[i].size(); j++){
            if(maps[i][j] == 'S') s= make_pair(i,j);
            else if(maps[i][j] =='L') l=make_pair(i,j);
            else if(maps[i][j] == 'E') e= make_pair(i,j);
        }
    }
    int a= goSearch(maps,s,l);
    if(a ==-1) return -1;
    int b= goSearch(maps,l,e);
    return b == -1 ? b: a+b;
    
}

 

그러나 문제가 발생했는데, core  dumped 에러가 몇개 발생했고 몇개는 시간초과가 발생했다. 원인을 분석해보니, visited[i][j] =1 로 변환하는과정을 queue에서 제거해서 검사할때 처리를 해준다. 이렇게 될 경우, 작업을 시작하기 전에 동일한 칸이 queue에 여러개 중복적재 될 수 있다는 점이다. 그래서 큐에 push 해주면서 visited 를  1 로 변경해야한다.

 

 

해결 방법 (성공 ) 

#include <string>
#include <vector>
#include <iostream>
#include <queue>
using namespace std;

int goSearch(vector<string>& maps, pair<int,int> start, pair<int,int> end){
    vector<vector<int>> visited(maps.size(), vector<int>(maps[0].size(),-1));
    queue<pair<int,int>> q;
    q.push(make_pair(start.first*1000 + start.second,0));
    
    while(!q.empty()){
        
        auto& crr = q.front();
        q.pop();
        int i  = crr.first /1000 ; int j = crr.first %1000; int dist = crr.second;    
        if(i == end.first && j == end.second) return dist;
    
        
        if(i-1 >= 0 && maps[i-1][j] != 'X' && visited[i-1][j] == -1){
            q.push(make_pair((i-1)*1000 + j,dist+1));
            visited[i-1][j] = 1;
        } 
        if(i+1 < maps.size() && maps[i+1][j] != 'X' && visited[i+1][j] ==-1){
            q.push(make_pair((i+1)*1000 + j, dist+1));
            visited[i+1][j]= 1;
        } 
        
        if(j-1 >= 0 && maps[i][j-1] != 'X' && visited[i][j-1] ==-1){
            q.push(make_pair(i*1000 + j-1,dist+1));
            visited[i][j-1] = 1;
        } 
        if(j+1 < maps[i].size() && maps[i][j+1] != 'X' && visited[i][j+1] ==-1){
            q.push(make_pair(i*1000 + j+1 , dist+1));  
            visited[i][j+1]= 1;
        }
        
    }
    
    return -1;
}

int solution(vector<string> maps) {
    pair<int,int> s, l , e;
   
    for(int i=0; i<maps.size(); i++){
        for(int j=0; j<maps[i].size(); j++){
            if(maps[i][j] == 'S') s= make_pair(i,j);
            else if(maps[i][j] =='L') l=make_pair(i,j);
            else if(maps[i][j] == 'E') e= make_pair(i,j);
        }
    }
    int a= goSearch(maps,s,l);
    if(a ==-1) return -1;
    int b= goSearch(maps,l,e);
    return b == -1 ? b: a+b;
    
}

 

 

마무리하며

큐에 대기줄을 추가할때 visited 의 값을 갱신하는 것이 BFS의 기본 규칙이라고 한다. 다음에 똑같은 문제가 나오면 잘 풀수 있을 것 같다.