[알고리즘_풀이] 프로그래머스 - 가장 먼 노드 java

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

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

프로그래머스 코드

import java.util.*;
     class Graph {
        class Node{
            int data;
            LinkedList<Node> adjacent;
            boolean marked;
            int count;
            Node(int data, int count) {
                this.data = data;
                this.marked = false;
                adjacent = new LinkedList<Node>();
                this.count = count;
            }
        }
         
        private Node[] nodes;
        Graph(int size) {
            this.nodes = new Node[size];
            for(int i=0; i<size; i++) {
                nodes[i] = new Node(i, 0);
            }
        }
        
        void addEdge(int i1, int i2) {
            Node n1 = nodes[i1];
            Node n2 = nodes[i2];

            if(!n1.adjacent.contains(n2)){
                n1.adjacent.add(n2);
            }
            if(!n2.adjacent.contains(n1)){
                n2.adjacent.add(n1);
            }
        }

        int bfs(int index) {
            int count = 1;
            Node root = nodes[index];
            Queue<Node> queue = new LinkedList<Node>();
            root.marked = true;
            root.count = count;
            queue.add(root);

            while(!queue.isEmpty()) {
                Node r = queue.remove();
                for(Node n: r.adjacent) {
                    if(n.marked == false) {
                        n.marked = true;
                        count = Math.max(count, r.count+1);
                        n.count = r.count + 1;
                        queue.add(n);
                    }
                }
            }
            
            return count;
        }
          
        int getNumOfNode(int max) {
            int rtn = 0;
            for(int i=0; i<nodes.length; i++) {
                if(nodes[i].count == max) {
                    rtn++;
                }        
            }
            return rtn;
        }
 
    }

class Solution {
    public int solution(int n, int[][] edge) {
        int answer = 0;
        
        Graph g = new Graph(n+1); // 1 ... n
        
        for(int i=0; i<edge.length; i++) {
            g.addEdge(edge[i][0], edge[i][1]);
        }
        
        int count = g.bfs(1);
        
        answer = g.getNumOfNode(count);
        
        return answer;
    }
}

 

IDE

import java.util.*;

class Graph {
	class Node {
		private int data;
		private boolean checked;
		private LinkedList<Node> adjacent;
		private int numFromRoot; // root로 부터 간선 개수
		
		Node(int data) {
			this.data = data;
			this.checked = false;
			this.adjacent = new LinkedList<>();
			this.numFromRoot = 0;
		}
	}
	
	private Node[] nodes;
	private int MaxLineLength = 0;

	Graph(int size) {
		this.nodes = new Node[size];
		for(int i=0; i<size; i++) {
			nodes[i] = new Node(i);
		}
	}
	
	void addEdge(int i1, int i2) {
		Node n1 = nodes[i1];
		Node n2 = nodes[i2];
		
		if(!n1.adjacent.contains(n2)) {
			n1.adjacent.add(n2);
		}
		
		if(!n2.adjacent.contains(n1)) {
			n2.adjacent.add(n1);
		}
	}
	
	void bfs(int rootData) {
		Node root = nodes[rootData];
		root.checked = true;
		root.numFromRoot = MaxLineLength + 1; 
		Queue<Node> queue = new LinkedList<>();
		queue.add(root);
		
		while(!queue.isEmpty()) {
			Node out = queue.remove();
			for(Node n: out.adjacent) {
				if(n.checked == false) {
					n.checked = true;
					n.numFromRoot = out.numFromRoot + 1;
					queue.add(n);
					MaxLineLength = Math.max(MaxLineLength, out.numFromRoot+1);
				}
			}
		}

	}
	
	void getFurthestNode() {
		for(int i=0; i<nodes.length; i++) {
			if(nodes[i].numFromRoot == MaxLineLength) {
				System.out.print(nodes[i].data + " ");
			}
		}
	}
	
	int getNumOfFurthestNode() {
		int count = 0;
		for(int i=0; i<nodes.length; i++) {
			if(nodes[i].numFromRoot == MaxLineLength) {
				count++;
			}
		}
		
		return count;
	}
}

public class Graph_Edge {
	public static void main(String[] args) {
		int n = 6;
		int[][] edge = {{3, 6}, {4, 3}, {3, 2}, {1, 3}, {1, 2}, {2, 4}, {5, 2}};
		
		Graph graph = new Graph(n+1); // 1 ~ n
		
		for(int i=0; i<edge.length; i++) {
			graph.addEdge(edge[i][0], edge[i][1]);
		}
		
		graph.bfs(1);
		System.out.print("가장 먼 노드 출력 : " );
		graph.getFurthestNode();
		System.out.println();


		System.out.println("가장 먼 노드의 개수 : " + graph.getNumOfFurthestNode());
	}
}