[프로그래머스] 가장 먼 노드- JAVA

n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.

노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 노드의 개수 n은 2 이상 20,000 이하입니다.
• 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.
• vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.

입출력 예

nvertexreturn

6

[[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]

3

입출력 예 설명

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

 

문제 분석 및 해결방안:

 

1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구한다고 내용에 적혀있다.

현재 그래프상에서는 

1 -> 5 까지의 간선의 길이 : 2

1 -> 6 까지의 간선의 길이 : 2

1 -> 4 까지의 간선의 길이 : 2

를 찾아서 반환 해주면 되는 문제였고 이건 BFS/DFS로 접근이 가능하다.

여기서 중요한건 양뱡향으로 연결을 시켜주면 절반은 푼거라고 생각하면 된다.

처음에 A번 노드와 B번 노드를 어떻게 연결을 시켜줄까 라는 생각을 미처하지못했다.

이부분은 ArraysList에 값을 담아서 해당 배열의 인덱스값을 list에서 꺼내서 노드의 넣으면 

A번 노드와 B번 노드가 담기고 LinkedList에 담기게 된다.

좀더 꼼꼼하게 보고 더 분석하는 연습을 하자 일단.

 

    static class Nodes {
        int n;
        int dist = 0;
        boolean visit = false;
        List<Nodes> links = new LinkedList<>();
        Nodes(int n) {
            this.n = n;
        }
    }
	
    List<Nodes> list = new ArrayList<>();
    int n = 6;

    // 각노드의 번호 저장
    for(int i = 1; i <= n; i++) {
        list.add(new Nodes(i));
    }

    // 간선의 배열 양뱡향 초기화 
    for(int[] e : edge) {
        Nodes n1 = list.get(e[0] - 1);
        Nodes n2 = list.get(e[1] - 1);

        n1.links.add(n2);
        n2.links.add(n1);
    }

   // BFS 처리
   int BFS() {

    // 가장 큰 길이 정의
    int maxDist = 0;
    Queue<Nodes> q = new LinkedList<>();
    // 0번째의 간선의 번호 
    q.get(list.get(0));
    
    while(!q.isEmpty()) {
       Nodes nodes = q.poll();
       
       for(Nodes node: nodes.links) {
       	  if(node.visit) continue;
          
          node.visit = true;
          // 현재 노드의 길이에서 1씩 증가하면 연결된 링크의 간선의 길이를 알수있다.
          node.dist = nodes.dist + 1;
          q.offer(node);
          
          maxDist = Math.max(maxDist, node.dist); 
       }
       
    }
   }
   
   int ans = 0;
   for(Nodes no: list) {
      if(node.dist == maxDist) ans++;
   }

 

내 노력이 헛되지 않기를 바라며 공부한다.