출처

해당 게시글은 [Java] 어서와! 자료구조 알고리즘은 처음이지?https://programmers.co.kr/learn/courses/13577를 간략히 요약한 게시글이며 모든 출처는 해당강의에 있습니다

---

문제

문제 분석

1번 노드로부터 가장 멀리 떨어진 노드들의 갯수를 구하는 문제입니다. 1번 노드로 부터 얼마나 떨어져 있는지 구해야 하므로 bfs, dfs를 사용하여 거리를 먼저 구해야 합니다.

---

풀이

나의 풀이

import java.util.*;

class Solution {
    public int solution(int n, int[][] edge) {
        int answer = 0;
        //bfs
        //1
        //3 2
        //6 4 5
        
        boolean[] visited = new boolean[n+1];
        int[] len = new int[n+1];
        List<Integer> list = new ArrayList<>();
        int root = 1;
        
        for(int i = 1; i <= n; i++){
            boolean allVisited = true;
            for(int j = 1; j <= n; j++){
                if(visited[j] == false) allVisited = false;
            }
            if(allVisited == true) break;
            
            for(int j = 0; j < edge.length; j++){
                if(edge[j][0] == root) len[edge[j][1]] = i;
            }
            
            list.clear();
            for(int j = 1; j <= n; j++){
                if(visited[j] == false && len[j] != 0) list.add(j);
            }
            
            System.out.println(list);
            
            for(int j = 0; j < list.size(); j++){
                visited[list.get(j)] = true;
            }
        }
        
        return list.size();
    }
}

visit 배열로 방문 여부를 체크하고 len 배열로 1번 노드와의 거리를 체크하려고 하였습니다.

1. visit = false, len = 0은 아직 방문 안한 노드
2. visit = false, len != 0은 이번 텀에 방문한 노드
3. visit = true, len != 0은 이미 방문했던 노드

로 구분하여 마지막텀에 방문한 노드들을 리스트에 한번에 받아 갯수를 리턴하려고 짰습니다

실패 이유

같은 길이에 존재하는 노드가 하나가 존재할 수 있지만 여러개 존재할 수도 있는 점을 간과하였었습니다.

문제의 예시처럼 1번 노드와 연결된 2번,3번 노드는 1번 노드와의 길이가 1이고 결국 다시 2번과 연결된 노드들, 3번과 연결된 노드들을 순서는 상관없지만 모두 한번씩 방문해야 했고 여러개가 나왔을때 모두 방문하는 로직을 고려하지 못하였었습니다.

강의의 풀이

import java.util.*;

class Node{
    int n;
    int dist = 0;
    boolean visit = false;
    List<Node> links = new LinkedList<>();
    Node(int n){ this.n = n; }
}

class Solution {
    public int solution(int n, int[][] edge) {
        List<Node> list = new ArrayList<>(); //노드의 리스트
        for(int i = 0; i < n; i++) list.add(new Node(i+1)); //리스트에 노드 추가
        
        // 노드간 간선 연결
        for(int[] e : edge){
            Node n1 = list.get(e[0] - 1);
            Node n2 = list.get(e[1] - 1);
            n1.links.add(n2);
            n2.links.add(n1);
        }
        
        int maxDist = 0;
        
        Queue<Node> queue = new LinkedList<>();
        Node first = list.get(0);
        first.visit = true;
        queue.offer(first);
        while(!queue.isEmpty()){
            Node now = queue.poll();
            
            for(Node node : now.links){
                if(node.visit) continue;
                
                node.visit = true;
                node.dist = now.dist + 1;
                queue.offer(node);
                
                maxDist = Math.max(maxDist, node.dist);
            }
        }
        
        int answer = 0;
        
        for(Node node : list)
            if(maxDist == node.dist) answer++;
        
        return answer;
    }
}

기존의 BFS를 그대로 활용하였습니다. 노드들간의 거리를 비교해야 하므로 노드객체에 1번 노드와의 거리를 저장하는 변수를 추가하고 방문시 기존의 거리를 +1씩 하며 저장하여 1번 노드와 멀어지는 노드일수록 1씩 증가하도록 하였습니다.

또한 마지막에 가장 긴 거리와 같은 거리를 가진 노드들의 갯수를 구하여 반환하였습니다.

---

Github

https://github.com/ds02168/Study_Algorithm/blob/main/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/%5BJava%5D%20%EC%96%B4%EC%84%9C%EC%99%80%20%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%9D%80%20%EC%B2%98%EC%9D%8C%EC%9D%B4%EC%A7%80/%ED%8C%8C%ED%8A%B89.Tree(%ED%8A%B8%EB%A6%AC)/%EA%B0%80%EC%9E%A5%EB%A8%BC%EB%85%B8%EB%93%9C.java