프로그래머스 [level3] 가장 먼 노드 ( BFS 알고리즘)

문제

#include <string>
#include <vector>
#include <deque>
#include <algorithm>

using namespace std;

int solution(int n, vector<vector<int>> edge) 
{
    int answer = 0;
   
    deque<int> m_deque; 
    vector<vector<int>> m_graph(n+1);
    vector<int> m_vecDist(n+1,-1);
    


    for(auto& iter : edge)
    {
        m_graph[iter[0]].push_back(iter[1]);
        m_graph[iter[1]].push_back(iter[0]);        
    }
    
    
    m_deque.push_back(1); 
    m_vecDist[1] = 0; 
    
    
    while(!m_deque.empty())
    {
        int CurNode = m_deque.front();
        m_deque.pop_front(); 
        
        for(auto& iter : m_graph[CurNode])
        {
            if(m_vecDist[iter] == -1)
            {
                m_vecDist[iter] = m_vecDist[CurNode] +1; 
                m_deque.push_back(iter);
            }
        }   
    }
    
    
    sort(m_vecDist.begin(), m_vecDist.end());
    
    for(auto& iter : m_vecDist)
    {
        if(iter == m_vecDist[m_vecDist.size()-1])
            answer++;
    }
    
    
    return answer;
}

 

문제 접근 순서

 

1. 일단 최단경로로 이동 했을 때 가장 긴 거리에 있는 노드가 몇개 있느냐를 목적으로 하는 문제로 

   처음 문제를 보자마자 아 이거 너비우선탐색 (BFS) 이구나 라고 생각했다.

   그 이유는 어떠한 시작점을 기준으로 최단거리로 가장 먼 곳이라는 목적지에 도착해야하므로 

   너비우선탐색을 통한 가장 먼곳에 도착하는 경우가 즉 최단경로로 갔다라는 의미니깐!

 

2. 여기서 중요한점은 양방향 그래프 이라는 점이다. 

    양방향 그래프 이기 때문에 각 노드마다 연결되어 있는 노드에 대한 정보를 넣어줘야한다.

    한쪽 방향으로만 정보를 넣어주면 BFS 탐색이 불가능하기 때문이다.

 

3. 따라서 BFS 구조이므로 while문과 queue 자료형을 사용하여 코드를 완성시켰다.