[알고리즘]프로그래머스 49189번 - 가장 먼 노드

프로그래머스 49189번 - 가장 먼 노드

프로그래머스 49189번 - https://programmers.co.kr/learn/courses/30/lessons/49189

 

요구사항

1. 주어진 그래프에서 1번 노드에서 가장 멀리 떨어진 노드의 개수를 반환하라.

 

요구사항 분석 및  풀이과정

1. 여기서 중요하게 봐야 할 점은 "최단 경로"의 정의이며, 그 이유는 최단 경로가 간선의 "개수"의 최솟값으로 정의된다는 점입니다.

 

i번 노드에서 j번 노드까지의 최단 경로 = i번 노드에서 j번 노드로 이동할 때 지나가는 간선의 개수가 작은 경로

 

2. i번 노드에서 j번 노드로 이동할 때, 다른 노드를 경유하여 올 경우 직접적으로 이동했을 때보다 최소한 하나의 간선을 더 지나치게 되며, 최단경로가 아니게 됩니다.

 

 

3. 1번 노드부터 BFS 알고리즘을 적용하여 j번 노드를 방문할 때, 이미 방문했다면 해당 노드를 처음 방문했을 때의 경로가 최단 경로이며, 방문하지 않은 노드라면 j번 노드 직전의 노드까지의 최단 경로에 방금 경유한 간선의 수(+1)를 추가하여 줍니다.

 

4. 3번을 수식으로 정리하면 다음과 같습니다. 

 

distance[i] = 1번 노드에서 i번 노드까지 최단 경로로 이동했을 때 간선의 개수

distance[k] = distance[i] + 1 ( k번 노드에 방문하지 않았고, k번 노드와 i번 노드 사이에 간선이 있을 경우 )

 

5. 만약 최단 경로의 정의가 간선의 개수가 아닌 간선의 가중치의 합이라면 BFS로 풀 수 없고, 최단거리 알고리즘으로 풀어야 합니다.

 

소스코드 작성

i번 노드의 방문 여부를 표현하기 위하여 방문하지 않았을 경우 임의의 큰 수(987654321)로 표현하겠습니다.

 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class Solution {

	public List<List<Integer>> makeGraph(int n, int[][] edges) {
		List<List<Integer>> graph = new ArrayList<>();
		for (int i = 0; i < n; i++) {
			graph.add(new ArrayList<>());
		}

		for (int[] edge : edges) {
			int from = edge[0] - 1;
			int to = edge[1] - 1;
			graph.get(from).add(to);
			graph.get(to).add(from);
		}

		return graph;
	}

	public int solution(int n, int[][] edges) {
		final int INF = 987654321;
		final int start = 0;

		List<List<Integer>> graph = makeGraph(n, edges);
		int[] distance = new int[n];

		Arrays.fill(distance, INF);

		Queue<Integer> q = new LinkedList<>();
		q.offer(start);
		distance[start] = 0;

		while (!q.isEmpty()) {
			int current = q.poll();

			for (int next : graph.get(current)) {
				if (distance[next] != INF) {
					continue;
				}

				distance[next] = distance[current] + 1;
				q.offer(next);
			}
		}

		int max = Arrays.stream(distance).max().getAsInt();
		return (int)Arrays.stream(distance).filter(v -> v == max).count();
	}
}

 

결과

 

소스코드 깃허브 주소

링크

 

소스코드 깃허브 주소

BFS를 이용하여 특수한 경우에 한해서 최단 경로(경로를 구성하는 간선들의 가중치의 합이 가장 적은 경로)를 구할 수 있는데, 그 경우는 간선의 가중치가 모두 동일한 경우입니다. 

 

간선의 가중치가 동일할 경우 이미 방문된 노드까지의 최단 경로는 다른 노드를 경유하여 방문하는 모든 경우보다 짧기 때문입니다.

 

이 문제를 BFS로 풀지 않고, 다익스트라 또는 벨만과 같은 최단경로 알고리즘으로 풀어도 상관없습니다.