그래프 - 가장 먼 노드, 1791. Find Center of Star Graph

코딩테스트 연습 - 가장 먼 노드 | Programmers School

프로그래머스

 

 

# 풀이 1

def solution(n, edge):
    graph = [[]for _ in range(n+1)]
    not_visited = [i for i in range(2, n+1)]
    for a, b in edge:
        graph[a].append(b)
        graph[b].append(a)
    

    far = {1}
    while not_visited:
        farther = set()
        for node in far:
            for j in graph[node]:
                if j in not_visited:
                    not_visited.remove(j)
                    farther.add(j)
        if not farther:
            return 1
        far = farther
    return len(far)

 

테스트 케이스 10개 중 1 개에서만 시간초과가 나옴.

 

 

 

 

# 바로 deque 도입한 풀이 2

from collections import deque

def solution(n, edge):
    graph = [[] for _ in range(n+1)]
    dist = [0]*(n+1)
    for i, j in edge:
        graph[i].append(j)
        graph[j].append(i)
    
    queue = deque([1])
    while queue:
        x = queue.popleft()
        if graph[x]:
            for k in graph[x]:
                if k == 1:
                    continue
                if dist[k] == 0:
                    dist[k] = dist[x]+1
                    queue.append(k)
    
    a = max(dist)
    answer = dist.count(a)
    
    return answer

 

시간 초과 없이 모든 테스트케이스를 통과했다.

 

 

 

 

 

 

 

 

 

 

Find Center of Star Graph - LeetCode

 

 

풀이 1

class Solution:
    def findCenter(self, edges: List[List[int]]) -> int:
        a, b = edges[0][0], edges[0][1]
        if a in edges[1]:
            return a
        else: 
            return b

 

 

풀이 2

class Solution:
    def findCenter(self, edges: List[List[int]]) -> int:
        if edges[0][0]== edges[1][0]:
            return edges[0][0]
        elif edges[0][0]== edges[1][1]:
            return edges[0][0]
        else:
            return edges[0][1]

 

 

두 번째가 조금 더 빨랐다..!