[Graph]: 그래프의 중심노드 구하기

문제

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

Find Center of Star Graph - LeetCode

접근방법

1. [단순 접근 방법] 주어진 인접리스트에서 가장 많이 등장한 노드를 테이블에 기록 후 list(dict.items())로 변환 한 뒤 내림차순으로 정렬한 첫 번째 요소 

2. [관계성을 이용한 접근 방법]: 별 모양 그래프에서는 첫 두 에지가 중심 노드를 공유 

 

코드 

1. 완전 탐색 

        

          

            

            

            

          
          
PYTHON
          
        
      from collections import defaultdict
class Solution:
    def findCenter(self, edges: List[List[int]]) -> int:
        table = defaultdict(int)
        for i in range(len(edges)): // 노드의 등장 횟수를 모두 기록
            table[edges[i][0]] += 1
            table[edges[i][1]] += 1
        ans = list(table.items())
        ans.sort(key = lambda x:x[1],reverse = True)
        return ans[0][0]

2. 두 인접 엣지의 관계성 파악 

        

          

            

            

            

          
          
PYTHON
          
        
      class Solution:
    def findCenter(self, edges: List[List[int]]) -> int:
        if edges[0][0] in edges[1]:  // 두 엣지간 공통 요소가 센터 노드
            return edges[0][0]
        return edges[0][1]