Programmers_Level2_게임 맵 최단거리

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

프로그래머스

 

---

 

 

문제를 보고 처음엔 DFS로 풀까 하다가 BFS로 풀기로 했다. 

이유는 첫째로 BFS를 익숙하게 쓰고 싶어서 이고 

둘째로는 DFS 모든 경로를 찾아 들어가고 그 중에 최단거리를 구해야하지만 

BFS의 경우 방문한 노드가 목적지라면 그때까지의 경로가 최단 거리를 보장한다. 

 

어째서 BFS로 탐색할 때 목적지에 도착하는 순간이 최단거리를 보장한다고 물으신다면..

BFS 복도식 아파트 같은 느낌이다. 

 

각 층을 방문할 때마다 복도의 모든 문을 확인한다. 

문을 열였을 때 다른 계단이 보이면 곧 방문할 리스트에 넣는다. 

한 층에서 모든 문을 확인 한 후에는 곧 방문할 리스트에서 하나의 계단을 선택해 올라간다. 

그리고 그걸 반복하는 것이 BFS이다. 

 

목적지가 복도에 있는 어느 하나의 문이라면 층수는 그 문까지 가는 최단 거리이다. 

각 층마다 모든 문을 확인하니 목적지를 발견하면 다른 층으로 갈 필요가 없으니 말이다. 

 

그래서 Class 를 사용하여 코드를 짰는데 테케는 맞았는데 막상 채점해보니 100점이 나오지 않았다. 

잉스러웠다... 

 

오답 코드 (73.7점) 

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

class findWay
{
    private: 
    vector<vector<bool>> visited; 
    vector<pair<int, int>> dir = {
        {-1, 0}, 
        {1, 0}, 
        {0, -1}, 
        {0, 1}
    };
    queue<pair<int,int>> myQ;
    int answer = -1;
    pair<int, int> cur = {0,0};
    pair<int, int> target; 
    pair<int, int> addPair(pair<int,int> a, pair<int,int> b)
    {
      return make_pair(a.first + b.first, a.second + b.second);  
    };
    
    public: 
    findWay(pair<int,int> endPoint)
    {
        this->target = make_pair(endPoint.first - 1, endPoint.second - 1);
        this->visited.resize(endPoint.first, vector<bool>(endPoint.second, 0));
    };
    void BFS(vector<vector<int>>& maps);
    int getAnswer(){ return answer; };
};


void findWay::BFS(vector<vector<int>>& maps)
{
    myQ.push(cur);
    
    while(!myQ.empty())
    {                
        pair<int, int> pos = myQ.front();
        myQ.pop();
        visited[pos.first][pos.second] = true;
        
        for(auto d : dir)
        {
            pair <int, int> temp = addPair(pos, d); 
            if(temp.first < 0 || temp.first > target.first ||
            temp.second < 0 || temp.second > target.second)
                continue;
         
            if(temp == target)
            {
                answer = maps[pos.first][pos.second] + 1;
            }
            
            if(!visited[temp.first][temp.second] && maps[temp.first][temp.second])
            {
                myQ.push(temp);
                visited[temp.first][temp.second] = true;
                maps[temp.first][temp.second] = maps[pos.first][pos.second] + 1;
            }
        }
    }
} 

int solution(vector<vector<int> > maps)
{
    int answer = 0;
    pair<int, int> target(maps.size(), maps[0].size());
    
    findWay finder(target);
    finder.BFS(maps);
    answer = finder.getAnswer();
    
    return answer;
}

 

 

프로그래머스에서는 따로 디버깅을 할 수 없어서 답답했는데 

밥먹고 오니 답이 보였다.. (밥힘?) 

 

내가 빼먹은 부분은 현재 방문한 노드가 목적지라면 BFS를 그만 해야했는데 

그 부분이 없어서 계속 탐색해 갔던 것이다. 

그래서 목적지까지 길이 하나밖에 없을 경우 정답처리가 되고 

목적지까지 여러 길이 있을 경우 계속 탐색을 해가니 최단거리가 아닌 결과가 나오는 것이다. 

 

정답 코드 (100점)

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

class findWay
{
    private: 
    vector<vector<bool>> visited; 
    vector<pair<int, int>> dir = {
        {-1, 0}, 
        {1, 0}, 
        {0, -1}, 
        {0, 1}
    };
    queue<pair<int,int>> myQ;
    int answer = -1;
    pair<int, int> cur = {0,0};
    pair<int, int> target; 
    pair<int, int> addPair(pair<int,int> a, pair<int,int> b)
    {
      return make_pair(a.first + b.first, a.second + b.second);  
    };
    
    public: 
    findWay(pair<int,int> endPoint)
    {
        this->target = make_pair(endPoint.first - 1, endPoint.second - 1);
        this->visited.resize(endPoint.first, vector<bool>(endPoint.second, 0));
    };
    void BFS(vector<vector<int>>& maps);
    int getAnswer(){ return answer; };
};

void findWay::BFS(vector<vector<int>>& maps)
{
    myQ.push(cur);
    
    while(!myQ.empty())
    {                
        pair<int, int> pos = myQ.front();
        myQ.pop();
        visited[pos.first][pos.second] = true;
        
        for(auto d : dir)
        {
            pair <int, int> temp = addPair(pos, d); 
            if(temp.first < 0 || temp.first > target.first || 
               temp.second < 0 || temp.second > target.second)
                continue;
         
            if(temp == target)
            {
                answer = maps[pos.first][pos.second] + 1;
                // 오답 코드에는 return이 없었다.. 
                return;
            }
            
            if(!visited[temp.first][temp.second] && maps[temp.first][temp.second])
            {
                myQ.push(temp);
                visited[temp.first][temp.second] = true;
                maps[temp.first][temp.second] = maps[pos.first][pos.second] + 1;
            }
        }
    }
} 

int solution(vector<vector<int> > maps)
{
    int answer = 0;
    pair<int, int> target(maps.size(), maps[0].size());
    
    findWay finder(target);
    finder.BFS(maps);
    answer = finder.getAnswer();
    
    return answer;
}

 

 

 

오답 코드 결과 (좌) / 정답 코드 결과 (중) / 리팩토링한 코드 (우)

 

클래스를 사용하지 않고 간결하게 리팩토링한 코드! 

#include<queue>
#include<vector>

using namespace std;

int solution(vector<vector<int> > maps)
{
    int answer = 0;
    pair<int, int> target = {maps.size() - 1, maps[0].size() - 1};
    vector<vector<bool>> visited(maps.size(), vector<bool>(maps[0].size(), false)); 
    vector<pair<int, int>> dir = {
        {-1, 0}, 
        {1, 0}, 
        {0, -1}, 
        {0, 1}
    };
    queue<pair<int,int>> myQ;
    
    myQ.push({0, 0});
    
    while(!myQ.empty())
    {                
        pair<int, int> pos = myQ.front();
        myQ.pop();
        
        for(pair<int,int> d : dir)
        {
            pair <int, int> temp = {pos.first + d.first, pos.second + d.second}; 
            
            if(temp.first < 0 || temp.first > target.first || 
               temp.second < 0 || temp.second > target.second)
                continue;
            
            if(!visited[temp.first][temp.second] && maps[temp.first][temp.second])
            {
                if(temp == target)
                {
                    return maps[pos.first][pos.second] + 1;
                }
                myQ.push(temp);
                visited[temp.first][temp.second] = true;
                maps[temp.first][temp.second] = maps[pos.first][pos.second] + 1;
            }
        }
    }
    return -1;
}