99클럽 코테 스터디 23일차 TIL + 그래프 Graph, [leetcode] Find Center of Star Graph

✨ 문제 

Find Center of Star Graph

There is an undirected star graph consisting of n nodes labeled from 1 to n. A star graph is a graph where there is one center node and exactly n - 1 edges that connect the center node with every other node.

You are given a 2D integer array edges where each edges[i] = [ui, vi] indicates that there is an edge between the nodes ui and vi. Return the center of the given star graph.

 

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

 

 

 

✨ 개념

그래프 Graph

- 여러 개의 노드 또는 정점들이 간선에 의해 연결된 자료구조.

 

그래프의 구성 요소

- 노드 (Node) : 데이터를 포함하는 개체. 그래프의 각 노드는 고유한 식별자를 가지며, 보통은 숫자나 문자열로 표현함.

- 간선 (Edge) : 노드들을 연결하는 선. 간선은 두 개의 노드 사이의 관계를 나타냄. 간선은 방향성이 있는 유향 그래프일 수도 있고, 방향성이 없는 무향 그래프일 수도 있음.

- 가중치 (Weight) : 간선에 할당된 추가 정보로, 간선의 비용이나 거리를 나타냄. 일부 그래프는 간선에 가중치를 할당하여 보다 복잡한 문제를 모델링할 수 있음.

 

 

✨ 최종코드

class Solution {
    public int findCenter(int[][] edges) {
        // 각 노드의 차수를 저장할 맵
        Map<Integer, Integer> degrees = new HashMap<>();
        
        // 각 간선에 대해 노드의 차수를 계산
        for (int[] edge : edges) {
            for (int node : edge) {
                degrees.put(node, degrees.getOrDefault(node, 0) + 1);
            }
        }
        
        int center = 0;
        int maxDegree = 0;
        
        // 차수가 가장 큰 노드를 중심으로 선택
        for (Map.Entry<Integer, Integer> entry : degrees.entrySet()) {
            if (entry.getValue() > maxDegree) {
                maxDegree = entry.getValue();
                center = entry.getKey();
            }
        }
        
        return center;   
    }
}