99 Club 2기 | Java | Beginner
⭐ 1791. Find Center of Star Graph
🏷 관련 주제 : Graph
Easy
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 1:
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.
Example 2:
Input: edges = [[1,2],[5,1],[1,3],[1,4]]
Output: 1
Constraints:
3 <= n <= 10⁵edges.length == n - 1edges[i].length == 21 <= ui, vi <= nui != vi- The given
edgesrepresent a valid star graph.
Accepted 191K | Submissions 228.3K | Acceptance Rate 83.7%
✔ Solution with 원소 직접 비교
class Solution {
public int findCenter(int[][] edges) {
int answer = 0;
int[] edge1 = edges[0];
int[] edge2 = edges[1];
for (int n1 : edge1) {
if (answer != 0) {
break;
}
for (int n2 : edge2) {
if (n1 == n2) {
answer = n1;
break;
}
}
}
return answer;
}
}채점 결과
✔ Solution with List, retainAll()
edges의 일차원 배열 2개를 List로 변환 후, 교집합을 구해서 공통 원소를 구하였다.
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
class Solution {
public int findCenter(int[][] edges) {
List<Integer> edge1 = Arrays.stream(edges[0]).boxed().collect(Collectors.toList());
List<Integer> edge2 = Arrays.stream(edges[1]).boxed().collect(Collectors.toList());
edge1.retainAll(edge2);
return edge1.get(0);
}
}채점 결과
✔ Solution with 노드 개수 세기
(노드의 값) - 1을 인덱스로 edge와 연결된 횟수를 세었다.
class Solution {
public int findCenter(int[][] edges) {
int answer = -1;
int n = edges.length + 1;
int[] cnt = new int[n];
for (int i = 0; i < n - 1; i++) {
cnt[edges[i][0] - 1]++;
cnt[edges[i][1] - 1]++;
if (i == n - 2) {
if (cnt[edges[i][0] - 1] == n - 1) {
answer = edges[i][0];
} else {
answer = edges[i][1];
}
}
}
return answer;
}
}채점 결과
💥 오늘 만난 문제 & 나의 시도 💦 & 해결 방법 👍
📌 오늘 만난 문제 : 별형 그래프는 하나의 중심 노드 가 있고 중심 노드를 다른 모든 노드와 연결하는 edge가 있는 그래프입니다. 방향이 없는 별 그래프가 각각 노드 와 사이에 edge가 있음을 나타내는 이차원 정수 배열 edges로 제공될 때, 주어진 별 그래프의 중심을 반환하시오
Star graph는 모든 노드가 중심의 노드와 연결되어 있으므로
edges에 들어있는 일차원 배열들은 공통의 원소 1개를 갖는다.
그리고 중심 노드 외에 다른 노드와는 연결되지 않으므로
일차원 배열 2개만 비교해도 중심노드를 얻을 수 있다.
그래서 배열의 공통원을 찾는 방법을 다음과 같은 방법으로 해결해 보았다.
1) 배열의 원소를 직접 비교
2) 로 변환 후, 교집합 구하기
이렇게 구했는데 뭔가 모든 edge들을 비교하지 않고 구하는 것이 꼼수같아서
3) 모든 edge들을 탐색하여 노드값을 세는 방법으로도 문제를 풀어 보았다.
💬 무엇을 새롭게 알았는지 
처음에 쓴 코드가 너무 꼼수같아서 여러 종류 코드를 써 보았는데
카톡을 보니 다른 분들께서 보내주신 짤들을 보고
'아... 다들 그렇게 쓰셨구나'
'코드가 꼭 무언가를 써야 하는 건 아닌걸까?' 하는 생각이 들었다.
하지만 문제에서 다루고있는 Topic은 알고 그 주제를 이용한 코드를 짤 수 있도록 공부해야겠다.
