[Swift] [82일차] 1791_LEETCODE 별그래프

1791. Find Center of Star Graph

---

문제 설명

1. 간선 그래프가 주어지고 edges의 길이는 node.count - 1
2. 가장 가운데에 있는 그래프 ( 모든 노드와 연결된 중심 노드의 번호를 출력)

---

문제 풀이

1. 일단 이거를 어떻게 카운팅해줄까하다가 배열에 SET을 노드 길이만큼 만들어주고,
2. 거기에서 이제 edges를 순회하면서 그래프에 적어준다음,
3. 그래프에 이제 각 간선에서 도달할 수 있는 노드를 카운팅해줬으니까 그 길이가 edges.count와 같으면 return 하는 방식으로 수행을 해줬다.

class Solution {
    func findCenter(_ edges: [[Int]]) -> Int {
        var graph = Array(repeating: Set<Int>(), count: edges.count + 1)

        for edge in edges {
            let a = edge[0] - 1
            let b = edge[1] - 1
            graph[a].insert(b)
            graph[b].insert(a)
        }

        var answer = 0
        for (idx, node) in graph.enumerated() {
            if node.count == edges.count {
                return idx + 1
            }
        }
        return 2
    }
}

맞긴했는데, 좀 많이 느린 것 같다. 일단 이게 겹칠일 없으니까 굳이 SET으로 해야할까?

class Solution {
    func findCenter(_ edges: [[Int]]) -> Int {
        var graph = Array(repeating: 0, count: edges.count + 1)

        for edge in edges {
            let a = edge[0] - 1
            let b = edge[1] - 1
            graph[a] += 1
            graph[b] += 1
        }

        var answer = 0
        for (idx, node) in graph.enumerated() {
            if node == edges.count {
                return idx + 1
            }
        }
        return 2
    }
}

58ms -> 13ms 로 감소한 것을 확인할 수가 있다.

최종 제출 코드

class Solution {
    func findCenter(_ edges: [[Int]]) -> Int {
        var graph = Array(repeating: 0, count: edges.count + 1)

        for edge in edges {
            let a = edge[0] - 1
            let b = edge[1] - 1
            graph[a] += 1
            graph[b] += 1
        }

        var answer = 0
        for (idx, node) in graph.enumerated() {
            if node == edges.count {
                return idx + 1
            }
        }
        return 2
    }
}

나름 최선으로 단순화시켰는데, 왜 이렇게 더 빠른 사람이 많지? 싶어서 다른 코드를 좀 살펴봤다.

---

타인의 코드

class Solution {
    func findCenter(_ edges: [[Int]]) -> Int {
        let firstEdge = edges[0]
        let secondEdge = edges[1]
        
        return secondEdge.contains(firstEdge[0]) ? firstEdge[0] : firstEdge[1]
    }
}

대체 어떻게 edges가 몇 개일지 모르는데도 edges[0], edges[1]만 확인하고 끝낼 수가 있지 ?

관련해서 좀 서칭을 해보니 찾아보니, 문제에서 언급하고 있는 <스타그래프>란 것의 특성때문이라는데, 여기서는 모든 노드와 연결되는 하나의 중심 노드가 있는 거니까, 그게 간선 두개만 쳐다봐도 둘다 포함되는 친구가 있다면 그게 바로 중심노드인 것이다. 그래서 딱 두 개의 간선만봐도 중심노드를 알 수 있다.
만약 가장 많은 노드와 연결된 노드를 찾는 문제였다면 나처럼 전체를 살펴봐야겠지만, 이번 문제처럼 스타 그래프의 중심 노드를 찾는 경우라면 이게 더 적합한 코드인 것이다.