그래프 / 가장 먼 노드

주어진 정점에서 최단경로로 이동시 가장 먼 정점들의 갯수를 구하는 문제로서, 노드와 엣지 & 가중치가 있기 때문에 다익스트라 알고리즘을 적용해야 하는 문제이다.

 

입력값은 정점들의 갯수와 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 과 같이 두 정점간 연결 상태를 제시한다.

 

해결단계는 크게 3단계로 나누었다.

1. 데이터 구조 마련
2. 알고리즘 적용하여 각 정점별 최단거리 추출
3. 최대값의 갯수 추출 (해)

각 단계에 대한 설명

• 데이터 구조 마련
  • arrange 함수에서 입력값을 알고리즘 적용에 용이하도록 구조를 짬
  • newEdge
    • 알고리즘이 알아들을 수 있는 데이터 구조 (dictionary 선언)
  • for _from, _to in edge
    • 입력값 내에서 쌍으로 되어있는 엣지 두개를 추출한다
  • {시작정점 : [끝정점 : 가중치]} 형태가 되도록 데이터를 채워간다
    • 양방향 노드이므로 정점의 순서를 바꿔서 채우기도 포함

def arrange(edge):
    newEdge = {}
    for _from, _to in edge:
        empty = [_to, 1]
        if not _from in newEdge:
            newEdge[_from] = []
        
        newEdge[_from].append(empty)

        empty = [_from, 1]
        if not _to in newEdge:
            newEdge[_to] = []
        
        newEdge[_to].append(empty)

    return newEdge

 

• 다익스트라 알고리즘

import heapq

def dijkstra(cnt, edge):
    # 최단거리 검색 시간을 O(N * log N) 수준으로 줄이기 위해 우선순위 큐를 이용할 것이고, 이를 위한 컨테이너
    arc = [] 

    # 시작정점에서 목표정점까지의 거리(가중치)를 담을 리스트 선언
    # 리스트의 인덱스 번호를 정점 번호(이름)로 간주할 것이므로 엣지 갯수 + 1 의 크기로 선언
    # distances[0] 은 0번 정점까지의 거리를 의미하는데, 문제에서 0번 정점은 존재하지 않는다.
    # 그러므로 유효한 값은 distances[1] ~ distances[정점갯수] 가 된다.
    # 우리는 이 distances 값을 구하는 게 목표이다.
    # 초기에는 각 정점까지의 거리를 알 수 없으므로 무한대 거리로 선언 - float('inf')
    # distances[1] = 0 은 시작점(1번 정점) 에서 1번 정점간 거리가 0이라는 의미이고, 
    # distances[2] = 1 는 시작점에서 2번 정점으로 가기까지의 거리가 1 이라는 의미이다. 
    distances = [float('inf') for i in range(cnt+1)]

    # 문제에서 시작점은 1로 고정이므로 distances[1] = 0 이 된다 (자기 자신과의 거리는 0 으로 설정)
    distances[1] = 0

    # 첫번째 인자는 넣을 데이터, 두번째 인자는 넣을 아이템인데, 만약 이값이 튜플이라면 튜플의 첫번째 요소를 우선순위 값으로 간주한다.
    # 이를 응용해 최소힙만 지원하는 heapq를 최대힙으로 바꿀수도 있다. (첫번째 인자에 -를 붙이면 됨)
    # 튜플의 첫번째 요소는 두번쨰 요소인 정점까지의 거리, 두번째 요소는 정점으로 설정하면
    # 우선순위인 거리에 의해 자동정렬되어 최단거리 검색 시간을 선형리스트를 쓰는 것에 비해 줄일 수 있다
    # 선형 리스트 O = N^2, 우선순위 큐 O = N * logN
    heapq.heappush(arc, (0, 1))

    # 큐에 더이상 값이 없을때까지 반복
    while arc:

        # 힙에서 뽑아낸 값은 튜플로서 (정점, 거리)
        current, distance = heapq.heappop(arc)
        
        # 만약 이미 저장된 정점까지의 거리보다 새로 뽑은 값이 크면 이미 최단 경로가 저장되어 있다는 의미이므로 넘긴다.
        if distances[current] < distance:
            continue

        # 위 arrange 함수에서 각 정점이 어떤 정점들과 연결되어 있는지 정리했으므로
        # 현재 정점과 연결되어있는 모든 정점의 거리를 추출한다. 
        for _next, _nextDist in edge[current]:
            # _next : 인접노드
            # _nextDist : 인접노드까지의 거리

            # 선택된 노드를 인접 노드로 거쳐서 가는 거리
            _nextDist += distance

            # 거쳐서 가는 거리가, 기존 거리보다 작으면 (짧으면) 최적 경로로 간주하고 비용 교체
            if _nextDist < distances[_next]:
                distances[_next] = _nextDist
                heapq.heappush(arc, (_nextDist, _next))

    # 유효한 값은 distances[1] 부터 이므로 짜른다
    return distances[1:]

 

• 최대값의 갯수 추출

def solution(n, edge):
    answer = 0
    distances = dijkstra(n, arrange(edge))
    maxDist = max(distances)
    for dist in distances:
        if dist == maxDist:
            answer += 1

    return answer