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

[13일차] 그래프 

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

* 대충 번역: 1부터 n까지 label된 n개의 노드를 가지는 무방향 star 그래프가 있다. Star 그래프는 하나의 중심(center)노드와 정확히 n-1개의 간선(edge)들이 있는 그래프이고, 다른 모든 노드들은 중심(center)를 연결한다. edges[i] = [u_i, v_i]가 u_i와 v_i사이의 간선을 의미하는 2차원 정수 배열 edges일 때, 주어진 그래프의 center를 반환하라.

My Solution

별모양 그래프여서 간선은 단 2개의 노드만 연결하며, 모든 노드들이 중심(center)노드와 연결된다는 점을 활용했다.

배열 전체를 돌면서 등장 횟수를 누적하고, 그 중 n회 등장한 노드가 곧 중심이 된다. (나머지 노드들은 전부 1회 등장할 것)

class Solution(object):
    def findCenter(self, edges):
        """
        :type edges: List[List[int]]
        :rtype: int
        """
        n = len(edges) + 1
        v = {}

        # 모든 노드를 초기화
        for edge in edges:
            v[edge[0]] = 0
            v[edge[1]] = 0
            
        # 아래처럼 라이브러리 사용도 가능
        # v = defaultdict(int)  # 기본값이 0인 딕셔너리

        # 간선 정보를 바탕으로 각 노드의 간선 수를 계산
        for edge in edges:
            n1 = edge[0]
            n2 = edge[1]
            v[n1] += 1
            v[n2] += 1

        # 간선 수가 가장 많은 노드를 반환
        return max(v, key=v.get)

Another Solution

그러나 사실, 해당 문제는 굉장히 단순하다. 별 모양 그래프의 특성을 활용하면 예외 없이 두 간선만 확인하여 바로 중심 노드를 알아낼 수 있다.

class Solution(object):
    def findCenter(self, edges):
        # 첫 두 간선을 확인하여 공통 노드를 찾는다
        n1, n2 = edges[0]
        n3, n4 = edges[1]
        
        if n1 == n3 or n1 == n4:
            return n1
        else:
            return n2

나다어

나의 초기코드는 아래와 같았다.

class Solution(object):
    def findCenter(self, edges):
        n = len(edges) + 1
        v = {1:0, 2:0, 3:0} # n => 3

        for i in range(1, n+1):
            n1 = edges[i][0]
            n2 = edges[i][1]
            v[n1] += 1
            v[n2] += 1

    return max(v)

이를 바탕으로 새롭게 배운 것들을 정리해 보자면, 

• 사전형 변수를 초기화하지 않으면 KeyError 가 발생한다.
  for문으로 초기화하는 과정도 결국 O(n)의 시간복잡도 이므로, 비효율적이지 않다!
• 시간을 아끼고 싶다면 defaultdict 라이브러리를 사용할 수 있다.
• value값이 최대인 key를 반환하려면, return max(v, key=v.get) 을 사용할 수 있다.