Programmers - 가장 먼 노드

---

title: Programmers - 가장 먼 노드
date: 2022-07-23
tags:

• Algorithm
• Graph

---

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

문제 요약

Graph가 주어진다. 1번 노드에서 가장 멀리 떨어진 노드의 개수를 count 한다.

문제 풀이

Graph를 순회하며 1번 노드에서 얼마나 떨어져있는지 확인하는 문제이다.
BFS 방식으로 각 노드를 확인하며, Priority Queue를 이용하여 거리를 기준으로 짧은 거리에 존재하는 노드부터 갱신한다.
여러 노드가 하나의 노드에 대한 emplace 작업을 할 경우, 이미 방문한 노드가 추후 Priority Queue에서 나올 수 있다.
erase 혹은 remove 작업을 하기 적합한 자료형을 가지지 않기에, 매번 top을 확인해야 한다.
현재 가장 긴 거리보다 길다면 거리를 갱신하고, 노드를 다시 0부터 count한다.


Graph를 이용한 문제들을 풀기 위해 입문하는 문제라고 볼 수 있다.
노드간의 경로에 대한 처리, Graph에서의 BFS 순회 등 응용 문제들을 풀기 위해 필수적으로 필요한 알고리즘 작성 및 구현을 할 줄 알면 쉬운 문제이다.

프로그램

#include <vector>
#include <utility>
#include <queue>
#include <stdio.h>

using std :: vector ;
using std :: pair ;
using std :: make_pair ;
using std :: priority_queue ;

#define PII pair < int , int >

struct pqPII
{
    int iNode ;
    int iCount ;

    pqPII ( int iNode , int iCount ) : iNode ( iNode ) , iCount ( iCount ) {}
} ;

struct comp
{
    bool operator () ( const pqPII & a , const pqPII & b )
    {
        return a.iCount > b.iCount ;
    }
} ;

int solution ( int n , vector < vector < int > > edge )
{
    vector < vector < int > > vPath ( n ) ;
    vector < int > * vpPathPointer = vPath.data () ;
    int iAnswer = 0 ;
    int iEdgeSize = edge.size () ;
    priority_queue < pqPII , vector < pqPII > , comp > pqBFS ;
    vector < bool > vVisit ( n , false ) ;
    int iCurrentMaxCount = 0 ;



    for ( int i = 0 ; i < edge.size () ; ++i )
    {
        int * ipTemp = edge [ i ].data () ;
        int iStart = * ipTemp ++ - 1 ;
        int iEnd = * ipTemp - 1 ;

        vpPathPointer [ iStart ].emplace_back ( iEnd ) ;
        vpPathPointer [ iEnd ].emplace_back ( iStart ) ;
    }

    pqBFS.emplace ( 0 , 0 ) ;
    while ( ! pqBFS.empty () )
    {
        while ( ( ! pqBFS.empty () ) && ( vVisit [ pqBFS.top ().iNode ] ) )            // Already visited pqBFS.top, pop
        {
            pqBFS.pop () ;
        }
        if ( pqBFS.empty () )                                                        // If no node to check, break
            break ;

        pqPII pTemp = pqBFS.top () ;
        pqBFS.pop () ;
        int iNode = pTemp.iNode ;
        int iCount = pTemp.iCount ;
        bool bCheckAll = true ;
        int iPathSize = vpPathPointer [ iNode ].size () ;
        int * ipPath = vpPathPointer [ iNode ].data () ;


        vVisit [ iNode ] = true ;

        if ( iCurrentMaxCount < iCount )                                            // Current node is new farthest
        {
            iCurrentMaxCount = iCount ;
            iAnswer = 1 ;
        }
        else if ( iCurrentMaxCount == iCount )
            ++ iAnswer ;

        for ( int i = 0 ; i < iPathSize ; ++i )
        {
            int iNextNode = * ipPath ++ ;

            if ( ! vVisit [ iNextNode ] )                                            // If didn't visited
                pqBFS.emplace ( iNextNode , iCount + 1 ) ;
        }
    }


    return iAnswer ;
}