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

해당 알고리즘 자료는 제가 직접 푼 것도 있지만 다른 분들의 풀이과의 비교를 통해 더 나은 알고리즘을 공부하기 위해 정리한 것들입니다.

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

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

풀이 1. (초급) - Node 클래스를 생성하여 for문을 통해 조건 체크
// 직관적이나 속도가 느리다.

import java.util.*;
class Solution {
    static class Node {
	int i = 0, cnt = 0;

	public Node(int i, int cnt) {
		this.i = i;
		this.cnt = cnt;
	}
}
    
    public int solution(int n, int[][] edge) {
       boolean [][] isStreet = new boolean [n][n];
	for (int i = 0; i < edge.length; i++) {
		isStreet[edge[i][0]-1][edge[i][1]-1] = isStreet[edge[i][1]-1][edge[i][0]-1] = true;
	}
	boolean [] vst = new boolean [n];
	int [] arr = new int [n];
	LinkedList <Node> qu = new LinkedList<Node>();
	qu.add(new Node(1, 0));
	int max = 0 ;
	while(!qu.isEmpty()) {
		Node node = qu.poll();
		if(vst[node.i-1]) continue;
		vst[node.i-1] = true;
		for (int i = 0; i < n; i++) {
			if(isStreet[node.i-1][i] && !vst[i]) {
				qu.add(new Node (i+1, node.cnt+1));
			}
		}
		arr[node.i-1] = node.cnt;
		max = Math.max(max, node.cnt);
	}
	int cnt = 0;
	for(int i : arr) if(max == i) cnt++;
        return cnt;
    }
}

풀이 2. (중급) - Queue와 List를 활용하여 조건 비교

import java.util.*;
class Solution {
    public int solution(int n, int[][] edge) {
        ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
	Queue<Integer> que = new LinkedList<Integer>();
		
	for (int i = 0; i <= n; i++) {
		list.add(new ArrayList<Integer>());
	}
	
	for (int i = 0; i < edge.length; i++) {
		int a = edge[i][0];
		int b = edge[i][1];
		list.get(a).add(b);
		list.get(b).add(a);
	}
		
	int [] cnt = new int [n+1];
	Arrays.fill(cnt, -1); // cnt 배열을 -1로 채우다.
	cnt[1] = 0;
	que.add(1);
	int node = 0;
		
	while(!que.isEmpty()) {
		node = que.poll();
		for(int i: list.get(node)) {
			if(cnt[i] == -1) {
				cnt[i] = cnt[node]+1;
				que.add(i);
			}
		}
	}
		
	int count = 0;
	int max = cnt[1]; // 0
	for(int i: cnt) {
		if(max < i) { // max가 아니면 다시 max를 잡아줘라
			max = i;
			count = 1;
		}else if (max == i ) { // max와 같으면 갯수를 추가
			count++;
		}
	}
        return count;
    }
}