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

https://school.programmers.co.kr/learn/courses/30/lessons/49189

프로그래머스

---

처음에 bfs로 풀다가 depth 카운팅이 이상해서 아닌가...? 하고

다익스트라로 풀려고 했는데 뭔가 bfs로 풀 수 있을 것 같은 느낌이 진허게 나서 결국 찾아봤따,,,

찾아보니 bfs로 풀 수 있더라구~

내가 bfs를 잘못 썼지 뭐야 ^^;

어차피 1번 노드부터 모든 노드까지의 최단 거리를 구해야하니까 출발지는 1번으로 하고 bfs로 모든 노드까지의 거리를 구해주면 되는 거였다!

 

풀이에서 신기했던 부분은 bfs를 구현할 때 depth를 queue에 같이 넣고 뺼 때 같이 뺴주는거였따!

막상 풀어보니까 그렇게 어렵지는 않았다!!

 

아 그리고 주의할 점은 내가 처음에 인접행렬로 풀려고 2차원 배열로 구현했는데, 그러면 메모리 초과가 발생한다

그래서 arrayList 배열을 사용한 인접 리스트로 풀면 시간도 빠르고 훨씬 메모리를 절약할 수 있었다!!

 

 

 

 

자바 코드)

package programmers;

import org.junit.Assert;
import org.junit.Test;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;


public class 가장먼노드 {
    static ArrayList<Integer>[] list;
    static int[] visit;
    static int max;

    public int solution(int n, int[][] edge) {
        int answer = 0;
        visit = new int[n+1];
        list = new ArrayList[n+1];
        for(int i=0;i<=n;i++) {
            list[i] = new ArrayList<>();
        }

        //그래프 간선 설정
        for(int[] e : edge) {
            int x = e[0];
            int y = e[1];
            list[x].add(y);
            list[y].add(x);
        }

        max = 0;
        bfs(1,0);
        
        for(int i=2;i<=n;i++) {
            if(max==visit[i]) {
                answer++;
            }
        }
       return answer;
    }

    private static void bfs(int start, int count) {
        Queue<Integer> q = new LinkedList<>();
        q.add(start);
        q.add(count);
        visit[start] = count;

        while (!q.isEmpty()) {
            int node = q.poll();
            int depth = q.poll();
            if(max<depth) {
                max=depth;
            }
            for(int i=0;i<list[node].size();i++) {
                int next = list[node].get(i);
                if(visit[next]==0) {
                    visit[next] = depth+1;
                    q.add(next);
                    q.add(depth+1);
                }
            }
        }
    }

    @Test
    public void test() {
        Assert.assertEquals(3, solution(6, new int[][] {{3,6},{4,3},{3,2},{1,3},{1,2},{2,4},{5,2}}));
    }
}