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

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

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

코딩테스트 연습 - 가장 먼 노드

풀이

최단경로로 이동하며 답을 찾아야 하는 문제이므로 BFS를 사용했다.

인접 행렬을 사용했는데, boolean이 아닌 int형으로 선언하면 메모리 초과가 난다. 인접 리스트로 구현하면 메모리 초과가 나지 않는다고 한다.

 

기본적인 BFS와 동일한데 중요한 점은 반환 값이 가장 멀리 떨어진 노드의 수 라는 점이다.

이를 위해 qSize로 큐의 크기를 저장해 마지막 큐의 크기를 반환하도록 구현하였다. 가장 멀리 떨어진 노드란 q가 반복될때 가장 마지막에 남아있는 노드를 의미하기 때문이다.

 

이를 위해서는 while문이 거리 만큼만 돌아야 하므로 for문을 사용해서 q에 있는 노드와 연결된 노드들이 한번에 처리될 수 있도록 하였다.  

 

코드

import java.util.*;
 
class Solution {
    public int solution(int n, int[][] edge) {
        boolean[][] node = new boolean[n + 1][n + 1];
        boolean[] memo = new boolean[n + 1];
        
        for(int i = 0; i < edge.length; i++) {
            int x = edge[i][0];
            int y = edge[i][1];
            node[x][y] = true;
            node[y][x] = true;
        }
        
        Queue<Integer> q = new LinkedList<>();
        q.add(1);
        memo[1] = true;
        int qSize = 1;
        
        while(!q.isEmpty()) {
            qSize = q.size();
            for(int i = 0; i < qSize; i++) {
                int temp = q.poll();
                for(int j = 2; j <= n; j++) {
                    if(memo[j] == false && node[temp][j] == true) {
                        memo[j] = true;
                        q.add(j);
                    }
                }
            }
        }
        return qSize;
    }
}