Programmers - 부대복귀

---

title: Programmers - 부대복귀
date: 2022-10-25
tags:

• Algorithm
• Graph
• Dijkstra

---

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

문제 요약

그래프가 주어지며, 출발 지점의 리스트와 하나의 도착 지점이 주어진다.
각 출발 지점에서 도착 지점까지 가는 경로의 최소 길이를 vector에 넣어 return한다. 경로가 없다면 -1을 넣는다.

문제 풀이

Node의 개수는 최대 100K이며, O(n^2) 이상이라면 TLE가 발생할 것이다.
출발 지점이 모두 달라 Bellman Ford Algorithm을 사용할 수 없다.
하지만 도착 지점이 하나이기에, 이를 역으로 생각하면 도착 지점에서 각 지점까지 가는 경로의 최소 길이를 구하면 된다.
이는 발상의 전환, 그리고 Dijkstra Algorithm을 의도한 문제임을 알 수 있다.


우선 주어진 경로를 넣는다. 처음에는 늘 이용하던 Adjacent Matrix를 이용하였으나, Node의 수가 너무 많아 불필요한 탐색이 반복되어 TLE가 발생하였다.
초기 경로의 최대 개수는 500K로, 평균적으로 한 Node당 5개밖에 조회를 하지 않는다.
Adjacent Matrix를 이용하며 균일된 500K의 초기 경로가 존재할 때, 최악의 경우 100K의 노드가 약 100K에 가까운 불필요한 탐색이 발생하는 것이다.
Adjacent List를 이용하는 방식으로 바꾸었다.
Dijkstra를 이용하기에 초기 Node를 도착 지점으로 넣으며, 아직 방문하지 않는 Node에 방문 가능할 경우 길이를 갱신해주고 queue에 넣는다.


발상의 전환을 하기까지 생각보다 오랜 시간을 소모하였다.
가중치가 없는 Undirected Graph이기에 출발 지점과 도착 지점의 구분을 하지 않아도 되는 문제인 것을 늦게 파악하였다.
또한 Adjacent Matrix를 편하게 사용하였으나, Adjacent List가 성능 측면에서 더 좋은 경우가 많을 수 있다는 것을 깨닫게 되었다.

프로그램

#include <vector>
#include <queue>

using std :: vector ;
using std :: queue ;

vector < int > solution ( int n , vector < vector < int > > roads , vector < int > sources , int destination )
{
    vector < int > answer ;
    vector < vector < int > > vPath ( n ) ;
    vector < int > vDest ( n , 1e5 ) ;
    int iRoadSize = roads.size () ;
    queue < int > qNode ;



    for ( int i = 0 ; i < iRoadSize ; ++i )
    {
        vPath [ roads [ i ] [ 0 ] - 1 ].emplace_back ( roads [ i ] [ 1 ] - 1 ) ;
        vPath [ roads [ i ] [ 1 ] - 1 ].emplace_back ( roads [ i ] [ 0 ] - 1 ) ;
    }

    qNode.emplace ( -- destination ) ;
    vDest [ destination ] = 0 ;

    while ( ! qNode.empty () )
    {
        int iNode = qNode.front () ;
        int iLength = vDest [ iNode ] ;
        qNode.pop () ;

        for ( int iTempDest : vPath [ iNode ] )
        {
            if ( 1e5 != vDest [ iTempDest ] )
                continue ;

            if ( iLength + 1 < vDest [ iTempDest ] )
            {
                vDest [ iTempDest ] = iLength + 1 ;
                qNode.emplace ( iTempDest ) ;
            }
        }
    }

    for ( int i : sources )
    {
        --i ;

        int iLength = vDest [ i ] ;

        if ( 1e5 <= iLength )
            iLength = -1 ;

        answer.emplace_back ( iLength ) ;
    }


    return answer ;
}