문제 바로가기
1에서 가장 먼 노드의 갯수를 찾는 문제
먼 기준은 최단거리기준 간선의 갯수
해당 그림에서는 4,5,6노드가 간선2개로 제일 멀다
따라서 3출력

접근방식의 오류

처음엔 dfs로 접근하려했다
for문을 2부터 노드갯수까지 돌려서 dfs쓸라했는데 그렇게 하면 방문했던곳을 또 방문하는 문제?가 생겨서 GPT한테 물어서 bfs로 갈아엎었다.

bfs를 한번만 돌려서 1부터 2,3,4,5,6노드에 접근할때까지의 간선의 갯수를 배열을 만들어서 하나씩 저장해나갔다.

정답코드

import java.io.*;
import java.util.*;

class Solution {
    static List<Integer>[] list;
    static int[] dist;
    static boolean[] visited;
    static int node2;
    static int max;
    
    public int solution(int n, int[][] edge) {
        int answer = 0;
        dist=new int[n+1];
        list=new ArrayList[n+1];
        for(int i=1;i<=n;i++){
            list[i]=new ArrayList<>();
        }
        for(int i=0;i<edge.length;i++){
            int a=edge[i][0];
            int b=edge[i][1];
            list[a].add(b);
            list[b].add(a);
        }
        
        visited=new boolean[n+1];
        bfs(1);
        
        // System.out.println(Arrays.toString(dist));
        for(int i=2;i<n+1;i++){
            if(dist[i]==max){
                answer++;
            }
        }
        return answer;
    }
    
    static void bfs(int node){
        Queue<Integer> q=new LinkedList<>();
        q.offer(node);
        visited[node]=true;
        
        while(!q.isEmpty()){
            int c=q.poll();
            for(int i:list[c]){
                if(!visited[i]){
                    visited[i]=true;
                    dist[i]=dist[c]+1;
                    max=Math.max(dist[i],max);
                    q.offer(i);
                }
            }
            
        }
        
    }
  
}

후기

언제 dfs를 쓰고 언제 bfs를 써야하는지 아직도 헷갈린다.
문제를 읽으면서 판단해나가야겠지...
오랜만에 그래프 문제를 풀었더니 재밌었다.