[프로그래머스]그래프 : 가장 먼 노드 (level 3)(c++)

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

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

 

c++ 코드

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

using namespace std;

int bfs_get_max_dist_cnt(vector<vector<int>> & adj_list, int n)
{
    // 0번노드에서 거리 1부터 시작
    // (거리가 0이 아니면 방문한 것으로 판단하기 위해)
    vector<int> dists(n);
    queue<pair<int, int>> q;
    q.push({0, 1});
    dists[0] = 1;
    int max_dist = 0;

    while (!q.empty())
    {
        int now = q.front().first;
        int dist = q.front().second;
        q.pop();

        // 인접 노드 중 아직 방문하지 않은 노드를 거리 + 1 한 후 큐에 push
        for (int i = 0; i < adj_list[now].size(); ++i)
        {
            int next = adj_list[now][i];
            if (dists[next] == 0)
            {
                // 0번 노드와의 거리 저장
                dists[next] = dist + 1;
                q.push({next, dist + 1});

                // 최대 거리 갱신
                max_dist = max(dist, max_dist);
            }
        }
    }

    // 0번 노드와 가장 먼 거리의 노드 개수 카운팅 후 반환
    int answer = 0;
    for (int i = 0; i < n; ++i)
    {
        if (dists[i] == max_dist)
        {
            ++answer;
        }
    }
    return answer;
}

int solution(int n, vector<vector<int>> edge) {

    // 인접 리스트 만들기
    vector<vector<int>> adj_list(n);
    for (int i = 0; i < edge.size(); ++i)
    {
        int A = edge[i][0] - 1;
        int B = edge[i][1] - 1;

        adj_list[A].push_back(B);
        adj_list[B].push_back(A);
    }

    // bfs탐색으로 가장 먼 거리의 노드 개수 구하기
    return bfs_get_max_dist_cnt(adj_list, n);
}

 

java 코드

import java.util.*;

class Solution {
    
    public int solution(int N, int[][] edges) {

        List<List<Integer>> adjacentList = new ArrayList<>();
        for (int i = 0; i <= N; ++i) {
            adjacentList.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            adjacentList.get(edge[0]).add(edge[1]);
            adjacentList.get(edge[1]).add(edge[0]);
        }

        return bfs(adjacentList, 1, N);
    }

    public int bfs(List<List<Integer>> adjacentList, int start, int N) {

        int max = 0;

        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        
        int[] dist = new int[N + 1];
        Arrays.fill(dist, -1);
        dist[start] = 0;

        while(!queue.isEmpty()) {

            int now = queue.poll();

            for (int next : adjacentList.get(now)) {

                if(dist[next] >= 0) {
                    continue;
                }

                dist[next] = dist[now] + 1;
                max = dist[next];
                queue.add(next);
            }
        }

        int maxCnt = 0;
        for (int d : dist) {
            if (max == d) {
                ++maxCnt;
            }
        }
        return maxCnt;
    }
}

 

 

1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다.
가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.

 

가장 먼 노드의 최단 경로를 구해서,

동일한 거리를 가지는 노드의 개수를 구하는 문제이다. 

따라서 bfs탐색이 적절하며, 시작 노드로부터의 거리를 메모이제이션 해주면 된다.