[프로그래머스(Programmers)][자바(java)] (Lv3) 가장 먼 노드

 

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번 노드 사이에 간선이 있다는 의미입니다.

 

입출력 예

n	vertex	return
6	[[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]	3

입출력 예 설명

예제의 그래프를 표현하면 아래 그림과 같고, 1번 노드에서 가장 멀리 떨어진 노드는 4,5,6번 노드입니다.

 

 

문제 풀이

import java.util.*;

public class Solution {
	
	class Node {
		int n, d;
		public Node( int n, int d ) {
			this.n = n;
			this.d = d;
		}
	}
	
	boolean v[];
	List<List<Integer>> e;
	
	public int bfs_findFarthest( int s ) {
		Deque<Node> q = new ArrayDeque<>();
		TreeMap<Integer, Integer> tm = new TreeMap<>();
		q.add( new Node( s, 0 ) );
		v[0] = true;
		int n, d;
		while( !q.isEmpty() ) {
			Node node = q.remove();
			n = node.n; d = node.d;
			if( tm.containsKey(d) )
				tm.replace( d, tm.get(d)+1 );
			else
				tm.put( d, 1 );
			for( int u : e.get(n) ) {
				if( !v[u] ) {
					q.add( new Node( u, d+1 ) );
					v[u] = true;
				}
			}
		}
		return tm.get( tm.lastKey() );
	}
	
	public int solution( int n, int[][] edge ) {
        	int i, s = edge.length, a, b;
        	e = new LinkedList<>();
        	for( i = 0; i < s; i++ )
        		e.add( new LinkedList<Integer>() );
        	v = new boolean[n];
        	for( i = 0; i < s; i++ ) {
        		a = edge[i][0]-1;
        		b = edge[i][1]-1;
        		e.get(a).add(b);
        		e.get(b).add(a);
        	}      
        	return bfs_findFarthest( 0 );
    	}
}

 

* BFS

- 인접 리스트 사용 ( 인접 행렬 사용 시 메모리 초과 ) -- 정점을 0부터 취급하기 위해 정점 번호를 1씩 뺌

- 트리 맵 사용 -- 거리를 key로 하고 각 거리의 노드의 개수를 value로 함

  ( TreeMap.lastKey() 함수는 값이 가장 큰 키를 반환하므로 거리가 가장 먼 것을 의미 )