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

https://programmers.co.kr/learn/courses/30/lessons/49189?language=cpp

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

풀이 방법

1번 노드와 가장 멀리 떨어진 노드들의 개수를 구하는 문제이다. BFS를 이용해 거리 별로 방문하다가 가장 마지막에 방문한 노드 개수를 반환하면 된다.

 

우선 노드의 개수가 최대 20,000개이고, 간선의 개수는 최대 50,000개이므로 간선 정보를 인접 행렬보다는 인접 리스트에 저장하는 게 더 효율적이다. 왜냐하면 인접 행렬은 크기가 20,000*20,000인 반면, 인접 리스트는 50,000이기 때문이다. 다음과 같이 인접 리스트를 초기화하면서 1번 노드와 인접한 노드들을 큐에 넣는다.

vector<int> adj[n+1];
for(const auto& e: edge){
    adj[e[0]].push_back(e[1]);
    adj[e[1]].push_back(e[0]);
    if(e[0] == 1){
        q.push(e[1]);
        visit[e[1]] = true;
    }
    else if(e[1] == 1){
        q.push(e[0]);
        visit[e[0]] = true;   
    }
}

 

그 후, 더 이상 방문할 노드가 없을 때까지 BFS를 실행하는데, 거리 별 노드 개수를 알아내기 위해 cnt 변수에 큐의 크기를 저장한다. 그리고 cnt 만큼만 큐에서 pop하면 1번 노드와 동일한 거리의 노드들만 for문으로 방문할 수 있다.

while(!q.empty()){
    cnt = q.size();
    for(int i=0; i<cnt; i++){
        int node = q.front();
        q.pop();
        for(int next: adj[node]){
            if(!visit[next]){
                q.push(next);
                visit[next] = true;
            }
        }
    }
}

 

while문이 종료되었을 때, cnt는 가장 거리가 먼 노드들의 개수를 저장하고 있을 것이다. 따라서 마지막에 cnt를 반환하면 답을 구할 수 있다.

 

전체 코드는 여기서 확인할 수 있다.