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

가장 먼 노드(Level 3)

문제

전체 문제 보기

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

접근법

문제에서 구해야하는 값은 "1번 노드에서 가장 멀리 떨어진 노드의 갯수"이다. 이 값을 구하기 위해 다음과 같이 접근한다.

• 모든 노드를 1번 노드부터 시작하여 너비우선 탐색(BFS)를 진행하면서, 각 노드에 깊이를 기록한다.
• 너비우선 탐색은 같은 깊이의 노드들을 먼저 탐색하고 한 단계 깊은 노드를 탐색하기 때문에 마지막 탐색한 노드의 깊이가 가장 멀리 떨어진 노드의 거리가 된다.
• BFS 탐색이 종료된 이후 마지막으로 탐색한 노드의 깊이와 같은 노드의 갯수를 카운트하여 반환한다.

 

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

using namespace std;

struct Node {
    Node()
        :mVisited(false)
        , depth(0)
    {}
    
    vector<int> mAdjacent;    // 인접 노드에 대한 정보
    bool mVisited;              // 방문 정보
    int depth;
};

int BFS(vector<Node>& graph)
{
    int answer = 0;
    int nextDepth = 1;  // 다음 노드의 깊이
    
    queue<int> q;
    
    // 1번 노드 부터 너비우선 탐색 시작
    graph[1].mVisited = true;
    graph[1].depth = 0;
    q.push(1);
    
    while(!q.empty())
    {
        int curNode = q.front();
        q.pop();
        
        // 현재노드의 깊이와 다음 노드의 깊이가 같다면, 깊이 값을 1증가시킨다.
        // 새로운 깊이 탐색 시작지점.
        if(graph[curNode].depth == nextDepth)
        {
            nextDepth++;
        }
        
        for(int ad : graph[curNode].mAdjacent)
        {
            if(graph[ad].mVisited == false)
            {
                graph[ad].mVisited = true;
                graph[ad].depth = nextDepth;
                q.push(ad);
            }
        }
    }
    
    // 탐색이 종료된 이후 마지막 탐색한 노드의 깊이와 깊이값이 같은 노드의 갯수를 카운트하여 반환
    for(auto node : graph)
    {
        if(node.depth == nextDepth - 1)
           answer++;
    }
    
    return answer;
    
}

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    
    // 그래프를 n+1개 선언한다.
    vector<Node> graph(n+1);
    
    // 각 노드의 인접노드를 연결한다.
    for(auto e : edge)
    {
        graph[e[0]].mAdjacent.emplace_back(e[1]);
        graph[e[1]].mAdjacent.emplace_back(e[0]);
    }
    
    return BFS(graph);
}