(Java)프로그래머스 코딩테스트 연습 - 그래프 - 가장 먼 노드

1. 문제

https://programmers.co.kr/learn/courses/30/lessons/49189?language=java

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

2. 나의 풀이

import java.util.*;

class Solution {
    
    static boolean [][] connect;
    static boolean [] checked;
    
    public int solution(int n, int[][] edge) {
        int ans = 0;
        connect = new boolean[n][n];
        checked = new boolean[n];
        for(int i = 0; i < edge.length; i = i + 1) {
        	connect[edge[i][0] - 1][edge[i][1] - 1] = true;
        	connect[edge[i][1] - 1][edge[i][0] - 1] = true;
        }
        
        Queue<Integer> q = new LinkedList<>();
        checked[0] = true;
        q.add(0);
        return bfs(q, n);
    }
    
    int bfs(Queue<Integer> q, int n) {
    	int cnt = 0;
    	while(!q.isEmpty()) {
    		int loop = q.size();
    		for(int i = 0; i < loop; i = i + 1) {
    			int cur = q.poll();
    			for(int j = 0; j < n; j = j + 1) {
    				if(connect[j][cur] && !checked[j]) {
    					q.add(j);
    					checked[j] = true;
    				}
    			}
    		}
    		cnt = loop;
    	}
    	return cnt;
    }
}

 - 처음에는 재귀를 사용하여 해결하려 했지만 시간 초과가 발생하여 노드 개수를 사용하여 그래프 메모리 확보 후 해결하는 방법을 사용(다른 분이 코딩한 코드를 바탕으로 코드를 해석하며 참고함)

3. 다른 사람 풀이

import java.util.ArrayList;

class Solution {
    public int solution(int n, int[][] edge) {
        ArrayList<Integer>[] path = new ArrayList[n];
        ArrayList<Integer> bfs = new ArrayList<Integer>();
        int answer = 0;
        int[] dist = new int[n];
        dist[0] = 1;
        int max = 0;

        for(int i = 0; i < edge.length; i++) {
            int num1 = edge[i][0] - 1;
            int num2 = edge[i][1] - 1;
            if(path[num1] == null)
                path[num1] = new ArrayList<Integer>();
            if(path[num2] == null)
                path[num2] = new ArrayList<Integer>();
            path[num1].add(num2);
            path[num2].add(num1);
        }

        bfs.add(0);
        while(!bfs.isEmpty()) {
            int idx = bfs.get(0);
            bfs.remove(0);
            while(!path[idx].isEmpty()) {
                int num = path[idx].get(0);
                path[idx].remove(0);
                bfs.add(num);
                if(dist[num] == 0) {
                    dist[num] = dist[idx] + 1;
                    max = dist[num];
                }
            }
        }
        for(int i = 0; i < n; i++) {
            if(dist[i] == max)
                answer++;
        }

        return answer;
    }
}