[99클럽 코테 스터디] 24일차 TIL 그래프

 

 

오늘의 문제는 LeetCode

 

1791. Find Center of Star Graph

 

 

문제

 

 

 

문제 설명 

n개의 노드로 구성된 무방향 성형 그래프가 있습니다. 해당 그래프는 중심 노드가 한 개이고 중심 노드와 다른 모든 노드를 연결하는 n - 1 개의 간선이 있습니다. 

2차원 배열 edges가 주어졌을 때 주어진 성형 그래프의 중심을 반환하면 되는 문제입니다. 

입출력 예시를 보면 edeges = [[1,2], [2,3], [4,2]] 일 때의 반환값은 2입니다. 

 

 

 

 

문제 풀이 시간 

권장 풀이 시간은 30분이었고, 저는 7분이 걸렸습니다.

 

 

 

문제 접근 방식

예시에서 알아봤듯이 다른 모든 노드와 연결되는 노드가 중심이 되는 노드입니다. 

중심 노드는 첫 두 간선에 공통으로 등장하는 노드이기 때문에 모든 요소를 비교할 필요가 없습니다. 2차원 배열에서 첫 번째 간선 edges[0]와 두 번째 간선 edges[1]의 노드를 비교해 같은 값을 찾으면 됩니다. 

 

 

 

 

문제 풀이

class Solution {
    public int findCenter(int[][] edges) {
        
        int answer = 0; 

        if(edges[0][0] == edges[1][0] || edges[0][1] == edges[1][0]) {
            answer = edges[1][0];
        } else {
            answer = edges[1][1];
        }
        return answer; 
    }
}

 

 

무방향 그래프(Undirected Gragh) 알아보기 

간선에 방향이 없는 그래프를 무방향 그래프라고 합니다. 정점 v와 점점 w를 연결하는 간선을 (v, w)라고 할 때, (v, w)와 (w, v)는 같은 간선이 됩니다. 왜냐하면 방향이 없기 때문이죠. 

정점이 n개 일 때 무방향 그래프가 가질 수 있는 최대 간선의 수는 n(n - 1) / 2 개 입니다. 

 

 

 

풀이 설명

1. 조건문 사용 : 첫 번째 간선의 두 노드 edges[0][0] 과 edges[0][1] 을 두 번째 간선의 첫 번째 노드 edges[1][0] 과 비교합니다. 만약 같은 노드가 있을 경우 그것이 중심 노드이기 때문에 answer에 값을 할당합니다. 

 

2. 대체 노드 비교 : 만약 위 조건이 성립하지 않을 시 남은 노드 edges[1][1] 이 중심 노드가 되므로 이를 answer에 할당하여 반환합니다. 

 

 

 

코드 개선하기 

현재 코드에서는 정답을 저장할 변수 answer를 선언한 뒤, 조건에 따라 값을 할당하고 있습니다. 그러나 이 변수는 사실 불필요한 과정입니다. 각 조건문에서 바로 return을 사용해 결과를 반환하는 것이 더 간결하고 효율적입니다.

 

 

 

 

 

 

 

이렇게 오늘 24일차 TIL을 작성해 보았습니다.