🖥️ 문제
There is an undirected star graph consisting of n nodes labeled from 1 to n. A star graph is a graph where there is one center node and exactly n - 1 edges that connect the center node with every other node.
You are given a 2D integer array edges where each edges[i] = [ui, vi] indicates that there is an edge between the nodes ui and vi. Return the center of the given star graph.
Example
Input: edges = [[1,2],[2,3],[4,2]]
Output: 2
Explanation: As shown in the figure above, node 2 is connected to every other node, so 2 is the center.
📝 풀이
class Solution {
public int findCenter(int[][] edges) {
int u1 = edges[0][0];
int v1 = edges[0][1];
if (u1 == edges[1][0] || u1 == edges[1][1]) {
return u1;
} else {
return v1;
}
}
}문제의 핵심은 스타 그래프에서 중심 노드를 찾는 것이다. 스타 그래프는 하나의 중심 노드와 그 외의 모든 노드가 이 중심 노드와 연결된 형태를 가진다.
그래서 첫 두 엣지를 비교해 공통된 노드를 찾았다. 첫 번째 엣지의 두 노드 중 하나가 두 번째 엣지와도 연결되어 있다면, 그 노드가 바로 중심 노드가 된다. 이는 스타 그래프의 특성상 가능하다. 두 엣지만 비교해도 중심 노드를 찾을 수 있기 때문에, 불필요한 연산을 줄이면서도 정확하게 답을 구할 수 있다.
👀 고찰
이 문제를 풀면서 중요한 건 복잡한 알고리즘을 적용하기보다는 주어진 데이터에서 간단한 패턴을 인식하는 것이었다. 스타 그래프의 특성을 이용해, 첫 두 엣지에서 공통된 노드를 찾아내는 방법을 떠올릴 수 있었다.
