[Algorithm] Programmers :: 가장 먼 노드

 

 

최장,최단노드들을 알아내야할 경우, 보통 BFS를 쓰는 경향이 있는것같아서 BFS로 풀어보았다.

그리고 인접행렬보다는 인접리스트를 쓰는게 좀 더 효율적인것같다. 이 문제같은 경우, 1번노드라는 특정노드에서 가장 먼 노드들을 찾는것이기 때문에 바로바로 노드들을 타고 내려가면서 distMap에 기록해야 하기 때문에, 인접리스트로 구현했다.

 

int solution(int n, vector<vector<int>> edge) 
{
    int answer = 0;
    vector<int> distMap(n + 1, -1); // dist[i]==> 1번노드에서 i번노드까지의 거리.
                                    // -1로 초기화한건 아직 방문안했다는 의미.
    queue<int> q;
    q.push(1); // 시작노드 넣어놓기.
    distMap[1] = 0; // 1번노드가 기준이므로, 자기자신은 0으로 세팅.
    vector<vector<int>> graph(n + 1); // 노드가 1부터시작해서 인덱스도 맞춰주는게 생각하기편함.
   
    for (int i = 0; i < edge.size(); i++) // 그래프 모델링.
    {
        int startNode = edge[i][0];
        int destNode = edge[i][1];
 
        graph[startNode].push_back(destNode);
        graph[destNode].push_back(startNode);
    }
    
    while (!q.empty())
    {
        int popedNode = q.front();
        q.pop();
 
        for (int connectedNode : graph[popedNode]) // graph[i] => i번 노드와 연결된 노드들이 담겨있는 vector.
        {
            if (distMap[connectedNode] == -1) // 아직방문안했으면
            {
                distMap[connectedNode] = distMap[popedNode] + 1; 
                q.push(connectedNode);
            }
        }
    }
 
    int maxNum = *max_element(distMap.begin(), distMap.end());
 
    for (int i = 0; i < distMap.size(); i++)
    {
        if (distMap[i] == maxNum)
        {
            answer++;
        }
    }
    
    return answer;
}