99클럽 코테 스터디 15일차 TIL

 

 

오늘의 공부 키워드

• 1791 Find Center of Star Graph

1791 Find Center of Star Graph

문제 해석

 이 문제는 n개의 노드(점)로 이루어진 무방향 스타 그래프에 관한 것입니다. 스타 그래프는 하나의 중심 노드가 있고, 나머지 n-1개의 노드가 그 중심 노드와 연결된 구조를 가집니다.

 

 edges라는 2차원 정수 배열이 주어집니다.  edges[i] = [ui, vi]는 노드 ui와 노드 vi 사이에 엣지가 있다는 것을 나타냅니다. 주어진 스타 그래프의 중심 노드를 반환하는 것이 이 문제의 목표입니다.

 

예시

예시 1:

입력: edges = [[1,2],[2,3],[4,2]]

출력: 2

설명: 노드 2는 다른 모든 노드와 연결되어 있으므로 중심 노드입니다.

예시 2:

입력: edges = [[1,2],[5,1],[1,3],[1,4]]

출력: 1

설명: 노드 1은 다른 모든 노드와 연결되어 있으므로 중심 노드입니다.

해결 방안

중심 노드를 찾기 위해서는 각 엣지에서 공통적으로 등장하는 노드를 찾으면 됩니다. 왜냐하면 스타 그래프에서 중심 노드는 모든 엣지에 등장하기 때문입니다. 아래의 방법으로 문제를 해결할 수 있습니다:

1. 첫 번째 엣지를 선택합니다. (edges[0])
2. 첫 번째 엣지의 두 노드 중 하나는 중심 노드입니다.
3. 두 번째 엣지에서도 이 두 노드 중 하나가 등장하는지를 확인합니다.
4. 등장한다면 그 노드가 중심 노드입니다.

코드

def findCenter(edges):
    # 첫 번째 엣지의 두 노드를 선택합니다.
    a, b = edges[0]
    
    # 두 번째 엣지에서 a 또는 b가 등장하는지를 확인합니다.
    # 만약 a가 등장하면 a가 중심 노드입니다.
    if edges[1][0] == a or edges[1][1] == a:
        return a
    # 그렇지 않으면 b가 중심 노드입니다.
    else:
        return b

# 예시 테스트
print(findCenter([[1, 2], [2, 3], [4, 2]]))  # 출력: 2
print(findCenter([[1, 2], [5, 1], [1, 3], [1, 4]]))  # 출력: 1

 

코드 설명

1. edges[0]에서 두 노드를 가져옵니다. 여기서 a와 b는 첫 번째 엣지의 노드입니다.
2. 두 번째 엣지(edges[1])에서 첫 번째 엣지의 노드 a 또는 b가 있는지 확인합니다.
   • 만약 a가 두 번째 엣지에 포함되어 있다면 a가 중심 노드입니다.
   • 그렇지 않다면 b가 중심 노드입니다.
3. 최종적으로 중심 노드를 반환합니다.

이 방법은 매우 효율적이며, 두 번째 엣지만 확인하면 중심 노드를 찾을 수 있으므로 O(1)의 시간 복잡도를 가집니다.

 

 

오늘의 회고

 

• 부족함을 느끼지만 실력을 늘리는것이 제일 빠른길임을 명심하자
• 새로운 개념을 배울수 있어서 좋았다.