[Programmers 코딩 연습] 가장 먼 노드 [Level 3]

문제(출처)-프로그래머스

알고리즘 기법

• bfs (or dfs)

자료구조

• 인접 그래프

설명

문제가 요구하는 것은 다음과 같다.

1. 1번 노드에서 시작하여 각 노드마다 최소 경로를 구한다.
2. 최소 경로들 중 최댓값의 개수를 구한다.

이를 위해서는 그래프를 탐색할 필요가 있으며 가장 기본적인 방법은 dfs와 bfs다.

dfs를 사용하든 bfs를 사용하든 2번 요구사항은 같은 방식으로 구하게 된다.
각 노드마다 최소 경로일 때의 간선 개수를 저장하고 그 값들을 비교하면된다.

그러나 1번 요구사항은 다르다.

dfs를 사용하는 경우 모든 경로를 탐색해야 한다.
예를 들어, 1번 노드에서 5번 노드로 간다고 할 때 갈 수 있는 모든 경로들을 비교해보고 최솟값을 정해야 한다. (1->2->5, 1->3->2->5, 1->3->4->2->5)

반면 bfs는 모든 경로들을 비교할 필요 없이 1->2->5 경로 하나만 살펴 보면 된다.
따라서 dfs 대신 bfs를 택하였다.

소스코드

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

using namespace std;

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    
    vector<vector<int>> graph = vector<vector<int>>(n+1);
    vector<int> cost = vector<int>(n+1, -1);
    //cost: array of # of edges in each path
    
    // create adjacent graph
    for (vector<int> link : edge) {
        int vtx1 = link[0], vtx2 = link[1];
        
        graph[vtx1].push_back(vtx2);
        graph[vtx2].push_back(vtx1);
    }
    
    int max_cost = 0;
    
    queue<int> que;
    que.push(1);
    cost[1] = 0;
    
    // bfs
    while(!que.empty()) {
        int vtx = que.front();
        que.pop();
        
        for (int vtx_next : graph[vtx]) {
            // if not visited
            if (cost[vtx_next] == -1) {
                cost[vtx_next] = cost[vtx] + 1;
                que.push(vtx_next);
                
                // update maximum cost
                if (max_cost < cost[vtx_next])
                    max_cost = cost[vtx_next];
            }
        }
    }
    
    // count maximum cost node
    for (int i = 1; i <= n; i++) {
        if (max_cost == cost[i])
            answer++;
    }
    
    return answer;
}

느낀점

bfs는 간선의 코스트가 모두 동일할 때 최소 경로를 탐색하는 효과가 있다.