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

https://programmers.co.kr/learn/courses/30/lessons/49189

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

 

문제 딱 보고 다익스트라네... 싶었는데

자세히보니까 bfs로도 충분히 풀 수 있을거라 생각해서 우선 bfs로 풀었다.

 

bfs는 재귀의 깊이의 최소값을 보장해줄것이기 때문에 각 노드별 갈 수 있는 거리의 최솟값을 뽑아줄것이다.

 

다익스트라는 구현연습용으로 풀어봤는데 뭐 잘 풀렸다!

한 노드에서 다른 모든 노드로 가는 최단거리를 구할수있어 다익스트라는!

 

 

 

bfs풀이와 결과

from collections import deque
 
 
def solution(n, edge):
    answer = 0
 
    graph = [[0] for _ in range(n + 1)]
 
    # 연결된 노드끼리는 연결. 가중치는 1
    for x, y in edge:
        graph[x].append(y)
        graph[y].append(x)
    li = []
 
    def bfs():
        q = deque()
        visit = [0] * (n + 1)
        # 몇 번 노드 방문인지, 거리는 얼마나되는지
        q.append([1, 0])
        visit[1] = 1
 
        while q:
            x, cnt = q.popleft()
            li.append(cnt)
            for y in graph[x]:
                if visit[y] == 1:
                    continue
                q.append([y, cnt + 1])
                visit[y] = 1
 
    bfs()
    max_cnt = max(li)
    answer = li.count(max_cnt)
 
    return answer

 

다익스트라 풀이와 결과

import sys
from heapq import heappush, heappop
 
 
def solution(n, edge):
    answer = 0
    INF = sys.maxsize
    graph = [[] for _ in range(n + 1)]
    # 최단거리 테이블 모두 무한 초기화
    distance = [INF] * (n + 1)
 
    for x, y in edge:
        graph[x].append([y, 1])
        graph[y].append([x, 1])
 
    def dijkstra():
        q = []
        # 1번노드 시작, 자기자신한테 가는 거리는 0
        heappush(q, [0, 1])
        distance[1] = 0
        while q:
            # 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
            dist, now = heappop(q)
            # 현재 노드가 이미 처리된적 있으면 continue
            if distance[now] < dist:
                continue
            for i in graph[now]:
                cost = dist + i[1]
 
                if cost < distance[i[0]]:
                    distance[i[0]] = cost
                    heappush(q, [cost, i[0]])
    dijkstra()
    max_cnt = max(distance[1:])
    answer = distance.count(max_cnt)
 
    return answer