99클럽 코테 스터디 : 깊이/너비 우선탐색(DFS/BFS) - 게임 맵 최단거리

TIL은 아니지만,,, 일단 기록은 남겨둬야할것같다

---

https://school.programmers.co.kr/learn/courses/30/lessons/1844#qna

아넘싫다,,,,, 자꾸 효율성에서 시간초과가 난다 짜증나!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

 

 

[DFS] - 효율성

#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;

void printmap(vector<vector<int>> maps){
    for(int i = 0; i<maps.size(); i++){
        for(int j = 0; j<maps[0].size(); j++){
            cout << maps[i][j] << " ";
        }
        cout << endl;
    }
}

// 1 지나갈 수 있는곳!
void gogogo(vector<vector<int>> maps,int a, int b, int sum, vector<int> &result){
    //당장 갈수있는 곳으로 한칸씩
    // 거기서 또 한칸씩
    // 상대팀 진영에 도착하면 지금까지 지나온 길 size를 result에 담고 리턴
    // 지금 루트에서 지나온길만 지나왔다는 표시를 해야함
    // (다른루트로 지나간곳은, 다시지나갈 수 있는것!)
    // map을 &로 보낼게 아니라, 칠한 새로운 map으로 보내주는걸 반복해야할듯
    // 앞뒤양옆 -> 지금위치는 a, b임!
    
    // 오른쪽, 아래순서로 가는게 가장 좋은것..!
    
    // 일단 왔으니까 못지나감표시 & sum 증가
    maps[a][b] = 0;
    //cout << "come (a, b) : "<<a<<", "<<b<<endl;
    //printmap(maps);
    sum += 1;
    
    // 지금 여기가 상대팀 진영이면 -> 리턴! (sum을 result에 담기)
    if((a == (maps.size()-1)) && (b == (maps[0].size() - 1))){
        result.push_back(sum);
    }
    
    
    
    if(a < (maps.size()-1) && maps[a+1][b] == 1){
        
        gogogo(maps, a+1, b, sum, result);
    }
    if(a > 0 && maps[a-1][b] == 1){
        
        gogogo(maps, a-1, b, sum, result);
    }
    if(b < (maps[0].size()-1) && maps[a][b+1] == 1){
        
        gogogo(maps, a, b+1, sum, result);
    }
    if(b > 0 && maps[a][b-1] == 1){
        
        gogogo(maps, a, b-1, sum, result);
    }
    // 어디로도 가지 않았으면 -> 더이상 이동할곳이 없음
    // 상대팀 진영에 도착한경우는 맨 처음에 걸리니까
    // 여기로 걸린경우는 그냥 막힌곳에 도달한것!
    // 아무것도 없이 리턴해준다 (result에 push할것도 없음)
}

int solution(vector<vector<int> > maps)
{
    int answer = 0;
    
    vector<int> result;
    gogogo(maps, 0,0,0,result);
    
    if(result.size() < 1){
        //result가 비어있다는건 상대팀으로 도착못했다는것
        answer = -1;
    }else{
        answer = *min_element(result.begin(), result.end());
    }
    
    return answer;
}

 

[BFS] - 효율성

#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;

void printmap(vector<vector<int>> maps){
    for(int i = 0; i<maps.size(); i++){
        for(int j = 0; j<maps[0].size(); j++){
            cout << maps[i][j] << " ";
        }
        cout << endl;
    }
}



int solution(vector<vector<int>> maps)
{
    int answer = 0;
    
    vector<vector<int>> que;
    // 시작은 [0][0]에서 -> 오른쪽 , 아래만 확인하기
    que.push_back({0,0,0});
    
    
    
    
    
    
    while(que.size() > 0){ // 큐가 차있을동안 반복!
        vector<int> now = que[0];
        int a = now[0];
        int b = now[1];
        int steps = now[2];
        
        maps[a][b] = 0; // 방문했음
        //cout << "come ("<<a<<", "<<b<<")"<<endl;
        que.erase(que.begin()); // 방문한곳 que에서 삭제
        //printmap(maps);
        steps++;
        
        if(a == (maps.size()-1) && b == (maps[0].size() - 1)){
            return steps;
        }
        
        if(b < (maps[0].size()-1) && maps[a][b+1] == 1){
            //cout<<"push ("<<a<<", "<<b+1<<")"<<endl;
            que.push_back({a,b+1, steps});
        }
        if(a < (maps.size()-1) && maps[a+1][b] == 1){
            //cout<<"push ("<<a+1<<", "<<b<<")"<<endl;
            que.push_back({a+1,b, steps});
        }
        if(a > 0 && maps[a-1][b] == 1){
            //cout<<"push ("<<a-1<<", "<<b<<")"<<endl;
            que.push_back({a-1,b, steps});
        }
        if(b > 0 && maps[a][b-1] == 1){
            //cout<<"push ("<<a<<", "<<b-1<<")"<<endl;
            que.push_back({a,b-1, steps});
        }
        
        
            
        
        
    }
    
    // 위에 if문에 걸려서 리턴이 안됐으면 상대팀을 못찾은것
    
    
    
    return -1;
}

---

[BFS] - 성공

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


int solution(vector<vector<int>> maps)
{
    int answer = 0;
    
    vector<int> dx = {1, -1, 0, 0};
    vector<int> dy = {0, 0, 1, -1};
    
    //vector<vector<int>> que;
    queue<vector<int>> que;
    // 시작은 [0][0]에서
    que.push({0,0, 0});
    
    int maxa = maps.size() -1;
    int maxb = maps[0].size() -1;
    
    
    while(que.size() > 0){ // 큐가 차있을동안 반복!
        //vector<int> now = que[0];
        int a = que.front()[0];
        int b = que.front()[1];
        int steps = que.front()[2];
        
        //maps[a][b] = 0; // 방문했음
        //cout << "come ("<<a<<", "<<b<<")"<<endl;
        
        //printmap(maps);
        
        
        if(a == maxa && b == maxb){
            return steps+1;
        }
        
        for(int i = 0; i<4; i++){
            int newa = a + dx[i];
            int newb = b + dy[i];
            if(newa > maxa || newb > maxb || newa < 0 || newb < 0){
                continue;
            }else{
                if(maps[newa][newb] == 1){
                    que.push({newa, newb, steps+1});
                    maps[newa][newb] = 0;
                }
            }
        }
        
        /*
        if(b < maxb && maps[a][b+1] == 1){
            //cout<<"push ("<<a<<", "<<b+1<<")"<<endl;
            que.push_back({a,b+1, steps+1});
            maps[a][b+1]=0;
        }
        if(a < maxa && maps[a+1][b] == 1){
            //cout<<"push ("<<a+1<<", "<<b<<")"<<endl;
            que.push_back({a+1,b, steps+1});
            maps[a+1][b]=0;
        }
        if(a > 0 && maps[a-1][b] == 1){
            //cout<<"push ("<<a-1<<", "<<b<<")"<<endl;
            que.push_back({a-1,b, steps+1});
            maps[a-1][b]=0;
        }
        if(b > 0 && maps[a][b-1] == 1){
            //cout<<"push ("<<a<<", "<<b-1<<")"<<endl;
            que.push_back({a,b-1, steps+1});
            maps[a][b-1]=0;
        }
        */
        que.pop(); // 방문한곳 que에서 삭제
        
    }
    
    // 위에 if문에 걸려서 리턴이 안됐으면 상대팀을 못찾은것
    
    
    
    return -1;
}

 

결론은 queue 라이브러리가 있으니까 que를 사용할때면 queue라이브러리에서 가져와야했다!

나는 그냥 vector를 그대로 이용해서 계속 효율성을 넘기지 못했던것같다..

 

왜이럴까,,,

일단 que랑 vector랑 서로 구현된게 다를것이고 (que가 뭔가 더 최적화가 되어있겠지)

아마 pop에서 큰 차이가 있지 않을까??

내가 알기로는 vector가 pop하는 부분 (즉 erase하는 부분)이 그 특정 인덱스 값을 vector의 맨 뒤로 옮기고, vector.end()를 한칸 땡겨서 구현된걸로 알고있다.

근데 que는 무조건 맨 앞 원소만 pop하니까 저런 불필요한 동작은 빠지고 뭔가 최적화가 되어있을것같다..

찾아봐야 하는데 여러모로 귀찮으니까 말아야지