99클럽 코테 스터디 24일차 TIL - Find Center of Star Graph

---

Find Center of Star Graph

출처 : LeetCode

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 <= 105
• edges.length == n - 1
• edges[i].length == 2
• 1 <= ui, vi <= n
• ui != vi
• The given edges represent a valid star graph.

---

틀린 풀이

이 풀이의 접근 방식은 두 가지 요소(엣지의 두 노드) 중 하나가 다음 엣지에도 포함되어 있는지 확인하는 것이다.

문제에서 제시하는 그래프

이미지 출처 : https://diseny.tistory.com/entry/2-%EB%85%B8%EB%93%9C%EC%9D%98-%EC%A4%91%EC%8B%AC%EC%84%B1centrality#google_vignette

/**
 * @param {number[][]} edges
 * @return {number}
 */
var findCenter = function(edges) {
    // 배열에 있는 원소 중 모든 원소에 등장한 원소를 출력하면 됨.
    // 앞에 있는 배열 2개 비교해서 공통원소 찾기
    let answer = [];
    for (let i = 0; i < edges.length; i++) {
        let [a, b] = edges[i]
        if (edges[i+1].includes(a)) {
        	answer.push(a) 
            return;
        } 
        if (edges[i+1].includes(b)) {
        	answer.push(b)
            return;
        }
    }
    return answer.split('').join('')
};

문제점은 다음과 같다.

1. if (edges[i+1].includes(a))와 if (edges[i+1].includes(b))에서 인덱스 i+1이 배열의 범위를 넘어갈 수 있다. 런타임 에러가 날 것이다.
2. return;으로 함수를 종료하면 맨 마지막 return으로 출력하는 값이 안 나온다. 너무 급하게 풀어서 이런 실수를 했다.
3. answer 배열 다음에 split('')와 join('')의 호출이 불필요하다.

틀린 풀이

 

올바른 풀이

break가 없어서 실행시간이 초과되는 풀이

/**
 * @param {number[][]} edges
 * @return {number}
 */
var findCenter = function(edges) {
    // 배열에 있는 원소 중 모든 원소에 등장한 원소를 출력하면 됨.
    // 앞에 있는 배열 2개 비교해서 공통원소 찾기
    let answer = [];
    for (let i = 0; i < edges.length - 1; i++) {
        let [a, b] = edges[i]
        if (edges[i+1].includes(a)) {
            answer.push(a) 
            console.log("answer", answer)
        }
        if (edges[i+1].includes(b)) {
            answer.push(b) 
            console.log("answer", answer)
        }
    }
    return answer[0]
};

break가 없는 풀이

 

for 루프를 통해 모든 엣지를 비교하고, 공통 노드를 answer 배열에 추가하게 되므로 시간이 많이 걸린다.

 

break를 추가한 풀이

/**
 * @param {number[][]} edges
 * @return {number}
 */
var findCenter = function(edges) {
    // 배열에 있는 원소 중 모든 원소에 등장한 원소를 출력하면 됨.
    // 앞에 있는 배열 2개 비교해서 공통원소 찾기
    let answer = [];
    for (let i = 0; i < edges.length - 1; i++) {
        let [a, b] = edges[i]
        if (edges[i+1].includes(a)) {
            answer.push(a) 
            console.log("answer", answer)
            break;  // 해당되면 반복 종료
        }
        if (edges[i+1].includes(b)) {
            answer.push(b) 
            console.log("answer", answer)
            break;  // 해당되면 반복 종료
        }
    }
    return answer[0]
};

def findCenter(edges):
    # 배열에 있는 원소 중 모든 원소에 등장한 원소를 출력하면 됨.
    # 앞에 있는 배열 2개 비교해서 공통원소 찾기
    answer = []
    for i in range(len(edges) - 1):
        a, b = edges[i]
        if a in edges[i + 1]:
            answer.append(a)
            print("answer", answer)
            break  # 해당되면 반복 종료
        if b in edges[i + 1]:
            answer.append(b)
            print("answer", answer)
            break  # 해당되면 반복 종료

    return answer[0]

# 사용 예시
print(findCenter([[1, 2], [2, 3], [4, 2]]))  #

break가 있는 풀이

해당하는 값을 찾으면 반복이 종료되므로 소모시간이 훨씬 적다.

 

더 효율적인 풀이

GPT가 제시해준 더 효율적이고 간단한 풀이를 가져왔다.

/**
 * @param {number[][]} edges
 * @return {number}
 */
var findCenter = function(edges) {
    // 배열에 있는 원소 중 모든 원소에 등장한 원소를 출력하면 됨.
    // 앞에 있는 배열 2개를 비교해서 공통 원소 찾기
    let [a, b] = edges[0];
    let [c, d] = edges[1];

    if (a === c || a === d) return a;
    else return b;
};

def findCenter(edges):
    # 배열에 있는 원소 중 모든 원소에 등장한 원소를 출력하면 됨.
    # 앞에 있는 배열 2개를 비교해서 공통 원소 찾기
    a, b = edges[0]
    c, d = edges[1]

    if a == c or a == d:
        return a
    else:
        return b

# 사용 예시
print(findCenter([[1, 2], [2, 3], [4, 2]]))  # 2

edges[0]의 첫 번째 값을 edges[1]의 두 가지 값과 각각 비교해서 같은 경우가 있는지 확인한다.

||(또는) 연산자를 쓰는 이유는, 한 배열에 노드가 2개 있기 때문에 1개만 같아도 연결이 되어있다는 의미이기 때문이다.