[프로그래머스] 가장 먼 노드(python 파이썬)

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

1번 노드로부터 가장 먼 길이의 노드의 개수를 찾는 문제입니다.

bfs을 이용한 풀이, dijkstra을 이용한 풀이 2개를 해보겠습니다.

 

1. bfs

bfs의 기본 원리는 가장 가까운 노드부터 방문합니다.

방문 표시를 위하여 vistied 변수를 만들고

큐에 (정점, 길이)를 추가하는 형식으로 진행합니다.

 

dfs & bfs 알고리즘에 대하여 궁금하신 분은 이 포스팅을 참고하시면 좋을 것 같습니다

[알고리즘] BFS & DFS

최대 길이, 개수 체크

큐에서 pop한 길이를 최대길이와 비교하여 더 클 경우 최대 길이를 d로 할당하고 개수를 1로 할당해줍니다.

만약 그렇지 않은 경우(현재의 최대길이와 같은 경우) 개수를 1 늘려줍니다.

        v,d = Q.popleft()
        if max_len<d:
            max_len = d
            max_cnt=1
        else:
            max_cnt+=1

전체코드

def solution(n, edge):
    from collections import deque
    answer = 0
    G = [[] for _ in range(n)]
    for a,b in edge:
        G[a-1].append(b-1)
        G[b-1].append(a-1)
    

    
    visited = [False for _ in range(n)]
    Q = deque()
    Q.append((0,0))
    visited[0] = True
    max_len = 0
    max_cnt = 0
    while Q:
        v,d = Q.popleft()
        if max_len<d:
            max_len = d
            max_cnt=1
        else:
            max_cnt+=1
        for next in G[v]:
            if not visited[next]:
                visited[next]= True
                Q.append((next,d+1))
        
    
    return max_cnt

 

 

 

2. dijkstra

dijkstra을 이용하여 풀어보겠습니다.

dijkstra의 기본 원리는 하나의 정점에서 다른 모든 정점까지의 거리를 계산할 수 있습니다.

heapq을 이용하여 시간 복잡도를 줄일 수 있습니다.

 

0에서 모든 정점까지의 거리를 체크하기 위하여 길이(D)를 INF로 초기화한 후 0번 노드의 값은 0으로 할당해줍니다.

이후, 현재 노드와 인접한 노드들(next)에 대하여 현재 길이보다 작은 경우 D값을 할당한 후 큐에 추가하는 형식입니다.

 

전체 코드

def solution(n,edge):
    import sys
    import heapq
    INF = sys.maxsize
    G = [[] for _ in range(n)]
    for a,b in edge:
        G[a-1].append(b-1)
        G[b-1].append(a-1)
        
    Q = []
    D = [INF for _ in range(n)]
    D[0] = 0
    heapq.heappush(Q,(0,0))
    while Q:
        w, v = heapq.heappop(Q)
        for next in G[v]:
            if D[next] > w+1:
                D[next] = w+1
                heapq.heappush(Q,(w+1,next))
    max_len = 0
    max_cnt = 1
    for d in D:
        if d>max_len:
            max_len = d
            max_cnt = 1
        elif d == max_len:
            max_cnt +=1 
    return max_cnt