[알고리즘] 가장 먼 노드

포인트

1. 가장 먼 노드 의미는 무엇인가? 
어떻게 보면 2가지로 해석을 할 수 있다.

• 1. BFS를 해서 제일 마지막 거리에 있는 노드들
• 2. 다익스트라 알고리즘을 써서 최단 거리가 max 인 것들의 노드들

2. 따라서 2가지 방법으로 풀 수 있습니다. 

🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 

BFS 

#include <string>
#include <vector>
#include <queue>
#include <cstring>
#include <tuple>
using namespace std;

vector<int> map[20010];
int dist[20010];

int bfs() {
	memset(dist, -1, sizeof (dist));
	int max_value = 0;
	queue<pair<int, int>> q;
	q.push ({ 1, 0 });
	dist[1] = 0; //거리를 이용하여 bfs 를 한다. dist 를 사용할 경우 visited 배열이 필요가 없다. 

	while (q.empty() == 0) {
		int x, value;
		tie (x, value)=q.front ();
		q.pop();

		for (int i = 0; i < map[x].size(); i++) {
			int nx = map[x][i];
			if (dist[nx] == -1) {
				dist[nx] = value + 1;
				q.push ({ nx, value + 1 });
				max_value=max (max_value, value + 1);
			}
		}
	}
	return max_value;
}

int solution(int n, vector<vector<int>> edge) {
	int answer = 0;
	for (int i = 0; i < edge.size(); i++) {
		int A = edge[i][0];
		int B = edge[i][1];
		map[A].push_back(B);
		map[B].push_back(A);
	}

	int value = bfs();
	for (int i = 2; i <= n; i++) {
		if (dist[i] == value) answer+=1;
	}
	return answer;
}

다익스트라 알고리즘 (min_heap 을 이용해서 구현)

#include <string>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

vector<int> map[20010];
int dist[20010];
int max_value;

void dijkstra() {
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
	pq.push ({ 0,1 });
	dist[1] = true;

	while (!pq.empty()) {
		int cost = pq.top().first;
		int x = pq.top().second;
		pq.pop();

		for (int i = 0; i < map[x].size(); i++) {
			int nx = map[x][i];

			if (dist[nx] > cost + 1) {
				dist[nx] = cost + 1;
				pq.push ({ dist[nx], nx });
				if (max_value < dist[nx]) max_value = dist[nx];
			}
		}
	}
}

int solution(int n, vector<vector<int>> edge) {
	int answer = 0;
	for (int i = 0; i < edge.size(); i++) {
		int A = edge[i][0];
		int B = edge[i][1];
		map[A].push_back(B);
		map[B].push_back(A);
	}
	for (int i = 1; i <= n; i++) dist[i] = 987654321;
	dijkstra();
	
	for (int i = 2; i <= n; i++) {
		if (dist[i] == max_value) answer+=1;
	}
	return answer;
}

어떻게 보면 BFS 하고 다익스트라하고 유사하고 다익스트라하고 프림하고 유사한 것을 알 수 있다.
잘 연결을 해서 기억을 하면 편하지 않을까 싶다. 

2021 03 09 추가

python

from collections import defaultdict


def bfs(start: int, distances: list, data: dict):

    q = [start]
    visited = set([start])

    while q:
        x = q.pop(0)
        for nx in data[x]:
            if nx not in visited:
                visited.add(nx)
                q.append(nx)
                distances[nx] = distances[x] + 1


def solution(n:int, edge:list):
    # 그래프 만들기
    data = defaultdict(list)

    for ele1, ele2 in edge:
        data[ele1].append(ele2)
        data[ele2].append(ele1)

    # bfs 탐색 (최단 거리를 구해야 하므로.)
    distances = [0]*(n+1)
    bfs(1, distances, data)

    max_distance = max(distances)

    return distances.count(max_distance)