1791. Find Center of Star Graph

안녕하세요! 스타 그래프의 중심 노드를 찾는 문제를 해결해보겠습니다.

1. 요구사항 명확화

- n개의 노드로 구성된 스타 그래프에서 중심 노드를 찾아야 함
- 스타 그래프는 하나의 중심 노드와 n-1개의 에지로 구성
- 중심 노드는 다른 모든 노드와 연결되어 있음
- 입력: 에지 배열 edges (각 원소는 [ui, vi] 형태의 연결 정보)
- 출력: 중심 노드 번호

2. 핵심 솔루션 설계

- 중심 노드는 모든 에지에 등장하므로, 가장 많이 등장하는 노드가 중심 노드
- 실제로는 두 개의 에지만 확인해도 중심 노드를 찾을 수 있음

3. 구현 상세

public class Solution {
    public int findCenter(int[][] edges) {
        // 첫 번째와 두 번째 에지만 확인하면 충분
        int[] edge1 = edges[0];
        int[] edge2 = edges[1];

        // 두 에지에서 공통으로 나타나는 노드가 중심 노드
        if (edge1[0] == edge2[0] || edge1[0] == edge2[1]) {
            return edge1[0];
        }
        return edge1[1];
    }
}

4. 주요 설계 결정

- 최적화된 접근: 전체 에지를 검사하지 않고 두 개의 에지만 확인
- 시간 복잡도: O(1)
- 공간 복잡도: O(1)

5. 검증 결과

테스트 케이스 1:
입력: [[1,2],[2,3],[4,2]]
결과: 2 (정확)

테스트 케이스 2:
입력: [[1,2],[5,1],[1,3],[1,4]]
결과: 1 (정확)

 

이 솔루션의 핵심 포인트는 다음과 같습니다:

• 스타 그래프의 특성상 중심 노드는 모든 에지에 반드시 포함됨
• 따라서 첫 두 에지만 확인하면 중심 노드를 찾을 수 있음
• 불필요한 반복이나 저장 공간을 사용하지 않는 효율적인 해결책

---

쉬운 설명

스타 그래프가 무엇인지 먼저 이해해볼까요?

예시:
     3
     |
 4 - 2 - 1
     |
     5

여기서 2가 중심 노드입니다. 모든 다른 노드들이 2와 연결되어 있죠.

문제를 쉽게 생각하면:

1. 중심 노드는 모든 선(에지)에 무조건 등장합니다
2. 다른 노드들은 딱 한 번만 등장합니다

그래서 아주 간단한 방법으로 풀 수 있습니다:

public class Solution {
    public int findCenter(int[][] edges) {
        // 첫 번째 선의 두 노드
        int a = edges[0][0];
        int b = edges[0][1];

        // 두 번째 선의 첫 노드
        int c = edges[1][0];

        // a가 두 번째 선에도 있으면 a가 중심
        if (a == c) return a;
        // b가 두 번째 선에도 있으면 b가 중심
        if (b == c) return b;

        // 아니면 두 번째 선의 다른 노드가 중심
        return edges[1][1];
    }
}

 

예를 들어보면:

입력: [[1,2],[2,3],[4,2]]
- 첫 번째 선: 1-2
- 두 번째 선: 2-3
- 2가 두 선에 모두 있네요! 
- 따라서 2가 중심입니다

 

이게 전부입니다! 첫 두 선만 보면 중심 노드를 바로 찾을 수 있어요.