Find Center of Star Graph

✏️오늘의 문제

💡나의 풀이

---

class Solution {
    public int findCenter(int[][] edges) {

        for(int i=0; i<edges.length; i++){
            for(int j=0; j<3; j++){
                if(j == 2){
                    return edges[0][1];
                }else if(edges[0][0] == edges[i][j]){
                    break;
                }
            }
        }

        return edges[0][0];
    }
}

주어진 코드는 그래프의 중심점을 찾는 함수 findCenter를 정의하고 있습니다. 이 함수는 주어진 간선 리스트 edges를 통해 중심 정점을 찾아 반환합니다. 코드의 작동 방식은 다음과 같습니다

1. 이중 루프: 첫 번째 루프는 edges의 각 간선을 순회합니다. 각 간선은 두 개의 정점으로 구성됩니다. 두 번째 루프는 인덱스 j를 통해 각 간선의 정점을 확인합니다.

2. 조건문

   • if(j == 2): 이 조건이 참일 경우, edges[0][1]을 반환합니다. 이는 첫 번째 간선의 두 번째 정점을 의미합니다.
   • else if(edges[0][0] == edges[i][j]): 첫 번째 간선의 첫 번째 정점이 현재 간선의 정점 중 하나와 일치하는지 확인합니다. 일치할 경우, 내부 루프를 종료합니다.

3. 반환값: 루프를 모두 돌고 나서도 반환되지 않았다면, edges[0][0]을 반환합니다. 이는 첫 번째 간선의 첫 번째 정점을 의미합니다.

문제점

이 코드는 실제로는 그래프의 중심점을 찾기 위한 정확한 로직이 아닐 수 있습니다. 그래프의 중심점은 연결된 정점 중 가장 많이 연결된 정점이기 때문에, 이 코드는 그 요구 사항을 충족하지 않을 수 있습니다. 중심점을 찾기 위해서는 각 정점의 연결 수를 세고, 가장 많이 연결된 정점을 찾아야 합니다.

💡더 효율적인 코드

그래프의 중심점을 올바르게 찾기 위한 코드의 문제를 해결하려면, 각 정점의 연결 수를 세고 가장 많이 연결된 정점을 찾는 방법을 사용할 수 있습니다. 다음은 그 문제를 해결한 코드입니다

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int findCenter(int[][] edges) {
        // 각 정점의 연결 수를 세기 위한 맵
        Map<Integer, Integer> degreeMap = new HashMap<>();

        // 간선을 순회하며 각 정점의 연결 수 증가
        for (int[] edge : edges) {
            degreeMap.put(edge[0], degreeMap.getOrDefault(edge[0], 0) + 1);
            degreeMap.put(edge[1], degreeMap.getOrDefault(edge[1], 0) + 1);
        }

        // 가장 많이 연결된 정점 찾기
        int center = -1;
        int maxDegree = 0;
        for (Map.Entry<Integer, Integer> entry : degreeMap.entrySet()) {
            if (entry.getValue() > maxDegree) {
                maxDegree = entry.getValue();
                center = entry.getKey();
            }
        }

        return center;
    }
}

코드 설명:

1. HashMap 사용: 각 정점의 연결 수를 저장하기 위해 HashMap을 사용합니다. 정점 번호를 키로, 연결 수를 값으로 저장합니다.

2. 간선 순회: 주어진 edges 배열을 순회하면서 각 간선의 두 정점에 대해 연결 수를 증가시킵니다. getOrDefault 메서드를 사용하여 해당 정점이 처음 등장할 경우 기본값 0에서 시작하게 합니다.

3. 최대 연결 정점 찾기: 모든 정점의 연결 수를 비교하여 가장 많이 연결된 정점을 찾습니다. 연결 수가 최대인 정점을 center 변수에 저장합니다.

4. 결과 반환: 가장 많이 연결된 정점인 center를 반환합니다.