Programmers[49189] - 가장 먼 노드[Level3]

링크

프로그래머스

문제설명

• 그래프 탐색, 거리가 가장 먼 node 갯수 구하기

문제풀이

• BFS depth별 탐색 마지막 반복횟수 리턴

문제코드

import java.util.LinkedList;

public class Solution {
    public static int solution(int n, int[][] edge) {
        int answer = 0;

        LinkedList<Integer>[] adj = new LinkedList[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new LinkedList<Integer>();
        }

        for (int[] v : edge) {
            int start = v[0]-1;
            int from = v[1]-1;
//            양방향 간선
            adj[start].add(from);
            adj[from].add(start);
        }


        boolean[] visited = new boolean[n];
        LinkedList<Integer> q = new LinkedList<Integer>();
        q.add(0);
        visited[0] = true;

        int now;
        while(!q.isEmpty()) {
            int qsize = q.size();
            answer = qsize;
            for (int i = 0 ; i < qsize; i++) {
                now = q.poll();
                for (int next : adj[now]) {
                    if(!visited[next]) {
                        q.add(next);
                        visited[next] = true;
                    }
                }
            }
        }

        return answer;
    }

    public static void main(String[] args) {
        System.out.println(solution(6, new int[][] {
            {3, 6}, {4, 3}, {3, 2}, {1, 3}, {1, 2}, {2, 4}, {5, 2}
        }));
    }
}

아쉬운 점

• q.isEmpty()문 빼먹음
• answer = qsize를 반복문 밖에 둬도 됨.(수정함)
  • qsize만큼 answer=qsize 반복안하게 할 수 있음

잘한 점

• foreach문 사용해서 linkedlist 탐색함