99클럽(2기) - 코테스터디 15일차 TIL # Graph

LeetCode - 1791. 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.

 

---

 

1. 나의 풀이

센터 노드는 모든 노든 edge가 공통으로 가지고 있으므로 첫 번째 edge와 두 번째 edge의 공통 요소만 찾으면 된다고 생각했다. 

 

1) 첫 번째 edge와 두 번째 edge를 set으로 형변환해서 교집합에 대한 요소 반환

 첫 번째 edge와 두 번째 edge의 교집합을 구한 결과를 pop() 하여 해당 요소를 반환한다. 

from typing import List
class Solution:
    def findCenter(self, edges: List[List[int]]) -> int:
        return (set(edges[0]) & set(edges[1])).pop()

 

 

2. 챗지피티의 풀이

 챗지피티도 나와 비슷한 방식으로 풀이했다. 대신 set 자료형을 사용하지 않고 두 edge의 요소들을 할당한 값들을 비교했다.

 

1) 첫 번째 edge, 두 번째 edge를 구성하는 요소들을 각 변수에 할당 

 첫 번째 edge의 두 요소를 a1, b1에, 두 번째 edge의 두 요소를 a2, b2에 할당한다.  

 

2) 일치하는 노드의 값 반환

 첫 번째 edge의 첫 번째 요소가 두 번째 edge의 요소들과 일치하는지 판단하고 일치하지 않으면 첫 번째 edge의 두 번째 요소를 반환한다. 

from typing import List

class Solution:
    def findCenter(self, edges: List[List:int]]) -> int:
        a1, b1 = edges[0]
        a2, b2 = edges[1]
        
        if a1 == a2 or b2:
            return a1
        else:
            return a2

 

 

3. 느낀점

 오늘은 꽤 쉽게 느껴졌다. 모든 edge를 순회하면서 공통되는 노드를 발견할 필요 없이 센터 노드는 무조건 모든 edge에 포함되어 있으니 첫 번째와 두 번째 edge만 탐색하면 끝나는 문제였다. 다만 챗지피티의 풀이가 집합 연산의 오버헤드를 방지하므로 조금 더 효율적이다. 물론 아무리 edge들이 많아져도 두 개의 edge만 비교할 것이라 별 차이 없겠지만!