[프로그래머스] 가장 먼 노드 C++

programmers.co.kr/learn/courses/30/lessons/49189

코딩테스트 연습 - 가장 먼 노드

 문제를 보고 떠오른 풀이는 다익스트라. 다익스트라로 풀어야되는 건 알겠는데 구현 방법은 생각나지 않았다.

GeeksForGeeks를 보는데 너무 길어서 programiz를 참고했다.

www.programiz.com/dsa/dijkstra-algorithm

Dijkstra's Algorithm

 이걸 보고서 구현하려고 하는데 노드와 에지를 다 만들어서 문제에 넣으려니 답답했다. 문제가 2차원 배열을 제시하므로 바로 넣으면 될 것 같기는 했는데, 코드로 구현하기는 어려워 여러 풀이를 참고하여서야 풀 수 있었다.

 

 0을 비워두고 1부터 시작하는게 나쁘지 않은 것 같은데, 찝찝해서 0부터 시작했다. 

 2차원 벡터를 사용하면 여러모로 편리한데, 노드와 에지 클래스를 구현하지 않아도 된다. 노드와 에지 클래스를 구현하고 거기에 필요한 Utility를 만들면 코드가 장난아니게 길어진다.

 그래서 2차원 vector에 노드를 대표하는 값을 넣고 푸는게 포인트. 아래에 있는 BFS풀이 방법과 다르게 거리가 줄어들 때만 계산하기 때문에 isVisited를 따로 체크할 필요는 없다.

 

 노드가 1부터 n까지 이므로 -1을 해주어 0부터 시작해 n-1까지 존재하는 것 바꾸었다.

---

 distance[i]는 0부터 i까지 최소 거리를 의미한다.  distance[0]을 0으로 초기화하고 queue에 넣어준다. N_Stack으로 인접한 노드를 확인하고 queue에 넣어준다. 만약 저장된 값보다 더 짧은 거리가 나오면 업데이트한다.

 다음 노드와 거리가 항상 +1이기 때문에 Dijikstra보단 BFS가 더 잘 어울리는 것 같다.

1. Dijikstra 풀이

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

// 배열이나 백터의 처음 할당할 때 .at()을 써서 배열의 범위를 초과할 경우
// Error 메세지를 반환하게 하였다.

void Dijkstra(vector<vector<int>> & Node_Stack, vector<int>& distance){
    queue<int> q;
    q.push(0);
    distance[0] = 0;
 
    while (!q.empty()){
        int cur = q.front();
        q.pop(); 

        for (int node:Node_Stack.at(cur)){
            if (distance.at(node) > distance.at(cur) + 1){
                distance[node] = distance.at(cur) + 1;
                q.push(node);
            }
        }
    }
}
 
int solution(int n, vector<vector<int>> edge) 
{
    vector<vector<int>> Node_Stack(n);
    vector<int> distance(n,50000);

    int answer = 0;
    
    // 인접한 노드를 모두 넣어준다.
    for (int i = 0; i < edge.size(); i++){
        int n1 = edge.at(i)[0]-1; // 0부터 시작하기 위해 1을 뺀다.
        int n2 = edge.at(i)[1]-1; //
        Node_Stack.at(n1).push_back(n2);
        Node_Stack.at(n2).push_back(n1);
    }
    
    Dijkstra(Node_Stack, distance);
    // 따로 bool compare(int,int)함수를 만들어도 되지만 람다를 사용해보았따.
    sort(distance.begin(), distance.end(),[](int a,int b){return a>b;});
    for (int i :distance)
        if (distance.at(0) == i) answer++;
    return answer;
}

 위에 참고한 사이트에 나타나있는 Djikstra 구현 코드가 되게 길었다. 코드 하나 하나 보면서 이해하려고 공을 들였는데 문제를 풀고 나니 굳이 볼 필요가 있었나? 의문이 들었다. 개념은 이미 알고 있었고 어떻게 구현하는 지를 봤는데, 2차원 벡터를 활용하여 노드간 연결관계를 나타낸 거면 굳이 노드 클래스를 따로 만들 필요가 없잖아? 이 노드를 다루기 위한 다양한 utility를 구현할 필요가 없잖아? 

언젠가 써먹을 일이 올거라 믿어야겠다.

---

 2. BFS 풀이

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>

using namespace std;
bool compare(int a, int b){
    return a>b;
}
int solution(int n, vector<vector<int>> edge) {
    vector<vector<int>> Node_Stack(n,vector<int>());
    vector<bool> isVisited(n,false);
    vector<int> distance(n,0);
    int answer = 0;
    
    for(vector<int> v:edge){
        int n1 = v.at(0)-1; // 0부터 시작하기 위하여 1을 뺀다.
        int n2 = v.at(1)-1; //
        Node_Stack.at(n1).push_back(n2);
        Node_Stack.at(n2).push_back(n1);
    }
    
    queue<int> q;
    q.push(0);
    isVisited[0] = true;
    while(!q.empty()){
        int cur = q.front();
        q.pop();
        for(int node:Node_Stack.at(cur)){
            if(!isVisited[node]){
                isVisited[node] = true;
                q.push(node);
                distance.at(node) = distance.at(cur)+1;
            }
        }
    }
    sort(distance.begin(), distance.end(), compare);
    for(int i:distance){
        if(distance[0]==i) answer++;
    }
    return answer;
}

 시작하는 노드 위치가 고정되어있기 때문에 BFS로 풀기 용이하다.

 

 직접 코드를 따라가며 예시를 만들어보고서야 distance.at(curr)+1의 의미를 알게 되었다.

항상 0에서 시작하기 때문에, 그 다음 방문지는 0과 연결되어 있는 노드다. 그 노드의 거리는 +1이 된다. 0과 직접 연결되어 있는 노드는 거리가 모두 1이 되고 그 다음 번 연결 된 노드를 방문한다. 이 노드들은 거리가 +1이 되어 2가 된다. 거리가 멀어지면서 +1이 되는 것이다.