리트코드 LeetCode find-center-of-star-graph

문제 

 https://leetcode.com/problems/find-center-of-star-graph/

Find Center of Star Graph - LeetCode

 

풀이

① edges는 노드의 갯수-1 개 만큼만 들어오기 때문에 모든 노드가 1개의 노드와 연결되어 있는... 중앙 집중형 네트워크 그래프이다. 

② 즉 모든 노드과 연결되는 노드를 구하면 된다. 

 

구현 JAVA

 

[그래프를 연결리스트로 구현]

import java.util.ArrayList;
import java.util.Collections;

class Solution {
    public int findCenter(int[][] edges) {
    
		
		ArrayList<ArrayList<Integer>> graph= new ArrayList<>(edges.length+2);
		for(int i = 0;  i < edges.length+2; i++) {
			ArrayList<Integer> row = new ArrayList<Integer>();
			row.add(i);
			graph.add(row);
		}
		
		for(int[] edge : edges) {
			graph.get(edge[0]).add(edge[0]);
			graph.get(edge[1]).add(edge[0]);
		}
		
		Collections.sort(graph, (o1, o2) -> (o1.size() - o2.size())*-1);
		
		return graph.get(0).get(0);
    }
    
}

 

[그래프를 배열로 구현]

노드를 인덱스로 하는 배열을 선언해 연결된 노드의 갯수를 저장한다.

저장된 노드의 갯수가 1 이상이면 그 노드가 Center이므로 그 노드를 return 한다.

class Solution {
    public int findCenter(int[][] edges) {
    
        int[] arr = new int[edges.length+2];
		for(int[] edge : edges) {
			arr[edge[0]] = ++arr[edge[0]];
			if(arr[edge[0]]>1) {
				return edge[0]; 
			}
			arr[edge[1]] = ++arr[edge[1]];
			if(arr[edge[1]]>1) {
				return edge[1];
			}
		}
        return 0;
    }
    
}