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

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

그래프의 가장 긴 깊이를 찾는 그래프 깊이 문제이다.

 

그래프 문제라고 해서 별 다른것이 아니라,

BFS를 통해서 가장 깊이있는 경우를 마지막에 출력하면 그 깊이를 알 수 있다.

 

check와 connect를 boolean으로 배열로 형성하여 방문했는지, 연결됐는지를 체크하는 용도로 사용한다.

이때 n이 아니라 n+1로 할당하는 이유는, 노드의 번호가 1부터 시작하기 때문이다.

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

class Solution {
    public int solution(int n, int[][] edge) {
        boolean[] check = new boolean[n+1];
        boolean[][] connect = new boolean[n+1][n+1];
        Queue<Integer> q = new LinkedList<Integer>();
        
        //connect에 연결된 부분을 모두 true로 바꿔놓는다.
        for(int i = 0; i<edge.length; i++){
            connect[edge[i][0]][edge[i][1]] = true;
            connect[edge[i][1]][edge[i][0]] = true;
        }
        check[1] = true;
        q.add(1);

        int answer =0;
        while(!q.isEmpty()){
            int qsize = q.size();

            for(int i =0; i<qsize; i++){
                int node = q.poll();

                for(int j =1; j<=n; j++){
                    if(connect[j][node]&&!check[j]) {
                        check[j] = true;
                        q.add(j);
                    }
                }
                System.out.println();
            }

            answer=qsize;

        }

        return answer;
    }
}

 

아래는 코드의 테스트 케이스이다.

테스트코드와 같다.

1에서 연결된 2,3을 Queue에 넣고

2를 Queue에서 뽑아서 4, 5를 Queue에 넣고

3을 Queue에서 뽑아서 5, 6을 Queue에 넣고

4,5,6을 순서대로 뽑아서 진행한다.

그러면 4,5,6이 마지막에 뽑힌 끝줄이므로 이때의 qSize가 답이된다.

테스트케이스

 

참고

in-intuition.tistory.com/23

[프로그래머스] 가장 먼 노드(java)[그래프]