파이썬으로 별(스타) 그래프의 중심 노드 찾기

문제 설명

1부터 n까지 번호가 매겨진 n개의 노드로 구성된 무방향 별(star) 그래프가 있다고 가정해 보겠습니다. 별 그래프란 하나의 중심 노드가 존재하고, 정확히 n-1개의 간선이 이 중심 노드를 나머지 모든 노드와 연결하는 형태의 그래프를 말합니다. 우리가 해야 할 일은 주어진 별 그래프에서 중심 노드를 찾는 것입니다.

예를 들어 입력이 아래 그림과 같다면,

노드 3이 그래프의 중심에 위치하고 있으므로 출력 결과는 3이 됩니다.

해결 접근 방법

이 문제는 다음 단계를 통해 해결할 수 있습니다:

seen := 새로운 집합(set) 생성
그래프의 각 간선 (u, v)에 대해 다음을 반복합니다:
- u가 이미 seen에 존재한다면 u를 반환
- v가 이미 seen에 존재한다면 v를 반환
- u를 seen에 추가
- v를 seen에 추가

이 방법이 작동하는 원리는 간단합니다. 별 그래프에서는 모든 간선이 반드시 중심 노드를 포함하기 때문에, 첫 번째 간선을 처리한 직후 등장하는 두 번째 간선과 겹치는 노드가 곧 중심 노드입니다. 따라서 전체 간선을 모두 확인하지 않고도 최대 두 개의 간선만 검사하면 답을 구할 수 있어 매우 효율적입니다.

예제

아래 파이썬 구현 예시를 통해 더 자세히 이해해 보겠습니다:

def solve(graph):
   seen = set()

   for u,v in graph:
      if u in seen:
         return u
      if v in seen:
         return v
      seen.add(u)
      seen.add(v)

graph = [(1,3),(2,3),(4,3),(5,3),(6,3)]
print(solve(graph))

입력

[(1,3),(2,3),(4,3),(5,3),(6,3)]