[프로그래머스/C++] 가장 먼 노드

미숙한 블로그 주인이 코딩테스트 문제를 풀어가는 과정을 담은 글입니다. 이 풀이가 효율적인 풀이가 아닐 수 있으며, 부정확한 정보가 많이 있을 수 있습니다. 보완해야할 점이 있다면 댓글로 남겨주세요!

 

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

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

가장 먼 노드

문제

n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.

노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

 

제한사항

• 노드의 개수 n은 2 이상 20,000 이하입니다.
• 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.
• vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.

 

풀이

입출력 예시

 

풀이

다익스트라 알고리즘을 사용할 줄 알면 쉽게 풀이가 가능한 문제였다. 각 노드까지의 거리를 1로 잡아서 1번 노드에서 각 노드까지의 최단 거리를 구한 뒤, 가장 멀리 떨어진 노드의 수를 구하면 됐다.

 

아래 코드에서는 주어진 간선들을 그래프로 표현한 뒤에, 다익스트라 알고리즘을 이용해서 최단거리를 구했다.

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

using namespace std;

const int INF = 9999999;

int dist[20001];
bool found[20001];
int grp[20001][20001];

int choose_vertex(int n) {
    int min_d = INF;
    int idx = -1;

    for (int i = 1; i < n; i++) {
        if (dist[i] < min_d && found[i] == false) {
            min_d = dist[i];
            idx = i;
        }
    }

    return idx;
}

void daijkstra(int n) {
    for (int i = 1; i < n; i++) {
        dist[i] = grp[1][i];
    }
    dist[1] = 0;
    found[1] = true;

    for (int i = 1; i < n; i++) {
        int u = choose_vertex(n);
        found[u] = true;

        for (int j = 1; j < n; j++) {
            if (found[j] == false) {
                dist[j] = min(dist[j], dist[u] + grp[u][j]);
            }
        }
    }
}

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    int max_d = 0;

    for (int i = 0; i < n + 1; i++) {
        dist[i] = INF;
        for (int j = 0; j < n + 1; j++) {
            grp[i][j] = INF;
        }
    }

    for (const auto& e : edge) {
        grp[e[0]][e[1]] = 1;
        grp[e[1]][e[0]] = 1;
    }

    daijkstra(n + 1);

    max_d = *max_element(dist + 1, dist + n + 1);

    for (int i = 1; i < n + 1; i++) {
        if (dist[i] == max_d) {
            answer++;
        }
    }

    return answer;
}