[c++] 프로그래머스 :: 가장 먼 노드 (문제 풀이, 코드)

가장 먼 노드

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

 

코드

#include <string>
#include <vector>
#include <set>
#include <queue>
#include <map>

using namespace std;

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    map<int, vector<int>> linked_list;
    set<int> list;
    list.insert(1);

    // 연결 리스트 만들기
    int size = edge.size();
    for(int i=0; i<size; i++){
        int first = edge[i][0];
        int second = edge[i][1];
        linked_list[first].push_back(second);
        linked_list[second].push_back(first);
    }

    queue<int> q; q.push(1);
    int q_size;
    while(list.size()!=n){
        q_size = q.size();
        for(int i=0; i<q_size; i++){
            int key = q.front(); q.pop();
            vector<int> tmp = linked_list[key];

            int size = tmp.size();
            for(int i=0; i<size; i++){
                auto ret = list.insert(tmp[i]);
                if(ret.second!=false)
                    q.push(tmp[i]);
            }
        }
    }
    answer = q.size();

    return answer;
}

 

설명

 우선 그래프 문제니까 배열로 풀지 연결리스트로 풀지를 생각했다. 배열로 풀게 되면 배열의 곱을 구해서 쉽게 풀 수 있겠지만, 배열을 표현하는 것부터 공간을 많이 차지하게 되고 배열의 곱 계산은 시간복잡도가 큰 계산 중 하나이다. 노드의 갯수 n이 20,000이하라는 조건에서 하나의 2차원 배열을 표현하기 위해 4x10^8의 공간이 필요한 것을 알 수 있고, 2차원 배열 2개를 곱하려면 10^17 정도의 시간복잡도가 소요된다. 보통 시간복잡도를 10^9 이하로 잡는데에 반하여 이는 굉장히 높은 수이므로 연결리스트를 이용한 표현법을 사용하기로 한다.

 

map<int, vector<int>> linked_list;

연결리스트를 구현하기 위해서 처음부터 구조체를 만들어서 구현해도 되지만 C++ 라이브러리인 STL에서 지원하는 map을 사용하기로 한다. key 값으로 노드 번호를 주고, value 값으로 해당 노드와 연결된 노드의 번호 배열인 vector 값을 주면 손쉽게 연결리스트를 구현할 수 있다.

 

set<int> list;
list.insert(1);

그 후, 연결리스트를 따라서 1번 노드부터 연결되어있는 노드들을 체크하면서 모든 노드가 체크될 때까지 진행해야한다. 이 때, 모든 노드에 들렀는지 체크하기 위해서는 비트마스크를 사용할 수도 있고, vector와 같은 배열에 표시할 수도 있다. 하지만 비트 마스크를 사용하기에는 n의 범위가 너무 커서 감당 가능한 자료형이 없고, vector를 사용하면 해당 원소가 이미 들렀던 원소인지를 찾는 데에 시간이 오래걸린다. 따라서 STL 라이브러리의 set을 이용하여 현재까지 들른 노드를 체크하도록 하였다.

 

 

 while(list.size()!=n){
        q_size = q.size();
        for(int i=0; i<q_size; i++){
            // queue에 있는 노드와 연결된 노드를 모두 처리
        }
 }

 코드 구현 시 주의해야할 점은 노드들을 BFS와 같은 형태로 순회하면 안된다는 것이다. BFS는 한번의 순회의 기준이 없이 queue가 빌 때까지 진행하는 방법으로, 이렇게 구현하게 되면 n개의 노드를 모두 순회한 순간 어떤 노드들이 마지막 순회에 포함되어있었는 지를 구분하기 어렵다. 따라서 while 내의 for문으로 단계를 나눠두었다.

 

 왼쪽 BFS 그림에서는 1번 노드와 연결된 2, 3번 노드를 queue에 넣은 후 2번 노드와 연결된 5번 노드를 queue에 넣는 과정을 순차적으로 실행하고 있다. 이렇게 구현하게 되면 3번은 1번 노드로부터 한 번의 연결로 도달할 수 있고 5번은 1번 노드로부터 2번의 연결로 도달할 수 있지만 이를 구분할 수 없게 된다.

 

 따라서 오른쪽 그림처럼 1번 노드와 연결된 2, 3번 노드를 queue에 넣은 후 2번과 3번 노드에 연결된 노드들을 queue에 모두 넣고 다음 단계로 넘어가게 하면 각 단계마다 1번 노드와 몇 번의 연결로 도달할 수 있는 노드들인지를 구분할 수 있다.

[비트마스크] : https://hini7.tistory.com/101

 

채점 결과

 

다른 사람의 풀이

 인접 배열로 그래프를 표현하되 queue를 사용하는 방식은 그래도 사용한 풀이가 꽤 많았다. 연결리스트를 이용한 방법은 STL 라이브러리를 더 import해야하기 때문에, 이 방법도 좋은 것 같다. (공간복잡도는 증가하겠지만)