99클럽 코테 스터디 24일차 TIL (Find Center of Star Graph) - LeetCode

1. 오늘의 학습 키워드

• 그래프

---

2. 문제: 1791. Find Center of Star Graph

• 단계: Easy
• 주제: Graph
• 출처: https://leetcode.com/problems/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.

Example 1:

Input: edges = [[1,2],[2,3],[4,2]]
Output: 2
Explanation: As shown in the figure above, node 2 is connected to every other node, so 2 is the center.

Example 2:

Input: edges = [[1,2],[5,1],[1,3],[1,4]]
Output: 1

Constraints:

• 3 <= n <= 105
• edges.length == n - 1
• edges[i].length == 2
• 1 <= ui, vi <= n
• ui != vi
• The given edges represent a valid star graph.

---

3. 나의 풀이

접근 방법

이번 문제는 star graph형태로 구성된 에지 리스트가 주어졌을 때, 그래프의 중심 노드를 찾으면 되는 비교적 간단한 문제입니다.

이 문제를 보자마자 networkx 라이브러리가 떠올랐지만, 안타깝게도 LeetCode에서 이 모듈을 지원하지 않아 다른 방법을 생각했습니다.

그런데 오히려 더 간단합니다.

말 그대로 중심 노드를 찾으면 되는데, 중심 노드는 모든 노드들과 연결이 되어있습니다.

따라서, 첫번째 에지 리스트에 있는 노드가 두번째 에지에도 있는지만 확인한다면 문제를 해결할 수 있습니다.

코드는 아래와 같습니다:

class Solution(object):
    def findCenter(self, edges):
        """
        :type edges: List[List[int]]
        :rtype: int
        """
        return edges[0][0] if edges[0][0] in edges[1] else edges[0][1]

결과

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

혹시, 추가적으로 networkx에 관심이 있으신 분들은 아래 링크를 참고하면 좋을것 같습니다.

NetworkX — NetworkX documentation

그리고 networkx 라이브러리를 활용해서도 한 번 풀어봤습니다. (LeetCode에서는 작동되지 않아, 개인적으로 돌려보았습니다.)

import networkx as nx
def find_star_center(edges):
    G = nx.Graph()
    G.add_edges_from(edges)
        
    # In a star graph, the center node is the one with the maximum degree
    
    degrees = dict(G.degree())
    center = max(degrees, key=degrees.get) # the key corresponding to the largest value in the degree dictionary.
        
    return center
    
print(find_star_center([[1,2],[2,3],[4,2]])) # 2
print(find_star_center([[1,2],[5,1],[1,3],[1,4]])) # 1

---

4. 결론

이번 문제는 그래프 관련 기초 문제였습니다. 이제 본격적으로 그래프 관련 문제를 풀 것 같네요.

읽어주셔서 감사합니다.