프로그래머스_가장 먼 노드(JAVA)

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

프로그래머스

[문제 풀이]

BFS(Breadth-First Search)를 이용하여 문제를 풀었습니다.

 

그래프의 거리, 가중치 등을 구하는 방법은 몇 가지가 있습니다. 대표적으로 다익스트라, MST, BFS 등이 있습니다. 해당 문제와 같이 가중치와 방향이 없는 무방향 그래프는 인접행렬 또는 인접그래프 형식으로 문제를 해결하는 경우가 많습니다.

문제에서 요구하는 것은 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하는 것을 요구합니다. 코드로 바로 설명 드리겠습니다.

1. 먼저, 2차원 배열 edge를 인접 리스트 형태의 그래프로 변환합니다.
   이를 위해 List<List<Integer>> 자료구조를 사용하고, graph 리스트를 초기화합니다.
2. edge 배열의 각 행을 순회하면서 양방향 간선에 대한 정보를 graph 리스트에 추가합니다.
3. BFS 알고리즘을 이용하여 1번 노드로부터 각 노드까지의 최단 거리를 구합니다. 
4. Queue<Integer> 자료구조를 이용하여 BFS를 구현하고, visited 배열과 distance 배열을 사용하여 이미 방문한 노드를 구별하고 해당 노드까지의 거리를 저장합니다. 초기에 1번 노드를 큐에 추가하고 방문 표시를 합니다.
5. 마지막으로, distance배열에서 가장 큰 값을 찾아 해당 노드까지의 거리인 max값을 구합니다. 그리고 distance배열에서 max와 같은 값을 가지는 노드들의 갯수를 세어서 결과값으로 반환합니다.

[JAVA]

import java.util.*;

class Solution {
    public int solution(int n, int[][] edge) {
			
			List<List<Integer>> graph = new LinkedList<>();
			
			for(int i = 0; i < n + 1; i++) {
				graph.add(new LinkedList<>());
			}
			
			for(int[] e : edge) {
				int a = e[0];
				int b = e[1];
				graph.get(a).add(b);
				graph.get(b).add(a);
			}
			
			boolean[] visited  = new boolean[n + 1];
			int[] distance = new int[n + 1];
			
			Queue<Integer> que = new LinkedList<>();
			que.add(1);
			visited[1] = true;
			while(!que.isEmpty()) {
				int cur = que.poll();
				
				for(int neighbor : graph.get(cur)) {
					if(!visited[neighbor]) {
						que.add(neighbor);
						visited[neighbor] = true;
						distance[neighbor] = distance[cur] + 1;
					}
				}		
				
			}		
			
			int max = 0;
			for(int item : distance) {
				if(max < item)
					max = item;
			}
			
			int answer = 0;
			for(int item : distance) {
				if(item == max)
					answer++;
			}	
			
			return answer;
	    }
}