최단 경로 알고리즘

가장 짧은 경로를 찾는 알고리즘

한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우 / 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 등의 사례가 해당

다익스트라 최단 경로 알고리즘

그래프에서 여러 개의 노드가 있을 때 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘

다익스트라 알고리즘의 원리

1. 출발 노드를 설정
2. 최단 거리 테이블을 초기화 (무한의 값 int(1e9사용)
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택 (그리디)
   : 가장 짧은 노드를 빠르게 찾을 수 있도록 힙 (heapq) 자료구조 사용
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신
5. 3,4번 과정 반복

heapq 시간복잡도

원소가 N개일때 원소의 삽입/삭제 : O(logN)

다익스트라 알고리즘 소스코드

# 개선된 다익스트라 알고리즘

import heapq
from sys import stdin
input = stdin.readline

# 노드의 개수, 간선의 개수
n, m = map(int, input().split(" "))

# 시작 노드 번호
start = int(input())

graph = [[] for _ in range(n+1)]

# 최단 거리 테이블 초기화
distance = [int(1e9) * (n+1)]

# 모든 간선 정보 입력
for _ in range(m):
    a,b,c = map(int, input().split(" ")) # a -> b 비용 : c
    graph[a].append((b,c)) # (도착노드, 비용 순서)

def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start)) # (비용, 노드). 힙은 0번째 요소를 기준으로 정렬하므로
    distance[start] = 0

    while q:
        dist, now = heapq.heappop(q)

        # 이미 처리된 노드라면 넘어가기
        # 현재 경로가 더 비용이 커 처리해줄 필요 X
        if distance[now] < dist:
            continue
            
        # 현재 노드와 연결된 다른 노드 보면서 최단거리 테이블 갱신
        for i in graph[now]:
            cost = dist + i[1]
            # cost가 더 작다면 업데이트
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))

dijkstra(start)

# 모든 노드로 가는 최단 거리 출력
for i in range(1, n+1):
    if distance[i] == int(1e9):
        print("INF")
    else:
        print(distance[i])

플로이드 워셜 알고리즘

그래프에서 여러 개의 노드가 있을 때 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우에 사용

단계마다 최단 거리를 가지는 노드를 찾을 필요 없이, 노드의 개수가 N개일때 N번의 단계를 수행하며 현재 노드를 거쳐가는 모든 경로를 고려한다. 따라서 O(N^3)의 시간복잡도를 가진다.

현재 노드(ex. k번 노드)를 제외하고, N-1개의 노드 중에서 서로 다른 노드 (A,B) 쌍을 선택한다. A -> k번 노드 -> B로 가는 비용을 확인한 뒤 최단 거리를 갱신한다.

다익스트라는 1차원 최단 경로 테이블을 가지나, 플로이드 워셜은 2차원 리스트를 통해 처리한다. (모든 노드에 대하여 다른 모든 노드로 가는 최단 거리 정보를 담아야 하므로)

플로이드 워셜 소스코드

from sys import stdin

input = stdin.readline

# 노드의 개수, 간선의 개수
n, m = map(int, input().split(" "))

# 2차원 리스트를 사용하여 그래프 초기화
graph = [[int(1e9)] * (n + 1) for _ in range(n + 1)]

# 자기 자신 -> 자기 자신 비용은 0으로 초기화
for i in range(1, n + 1):
    for j in range(1, n + 1):
        if i == j:
            graph[i][j] = 0

# 각 간선 정보 입력받기
for _ in range(m):
    # a -> b 비용 : c
    a, b, c = map(int, input().split(" "))
    graph[a][b] = c

# 노드i -> 노드k -> 노드j 거쳐가는 것과 vs 현재거리 (i->j) 중 짧은 요소로 업데이트
for k in range(1, n + 1):
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

# 결과 출력
for i in range(1, n + 1):
    for j in range(1, n + 1):
        if graph[i][j] == int(1e9):
            print("INF", end=" ")
        else:
            print(graph[i][j], end=" ")
    print()

Lv 3. 가장 먼 노드

풀이

다익스트라 알고리즘을 사용하여 풀면 되는 문제다. 문제 조건 상 그래프는 양방향 연결 그래프이며, 간선의 weight는 1이다.

따라서 다익스트라 알고리즘을 통해 최단 경로 테이블을 업데이트해준 뒤, 가장 거리가 긴 노드가 총 몇개인지 체크해주면 된다. (단순히 max() 함수를 쓰다간 int(1e9) 값이 최댓값이 되어버리니 주의!

코드

import heapq

def solution(n, edge):
    answer = 0
    
    graph = [[] for _ in range(n+1)]
    for a,b in edge:
        graph[a].append((b, 1)) 
        graph[b].append((a, 1)) 
    
    # 최단 경로 테이블
    distance = [int(1e9) for _ in range(n+1)]
    
    def dijkstra(start):
        q = []
        heapq.heappush(q, (0, start))
        distance[start] = 0
        
        while q:
            dist, now = heapq.heappop(q)
            
            if distance[now] < dist:
                continue
            # 연결된 노드 살펴보기
            for i in graph[now]:
                # 비용 업데이트
                cost = dist + i[1]
                if cost < distance[i[0]]:
                    distance[i[0]] = cost
                    heapq.heappush(q, (cost, i[0]))
    dijkstra(1)
    max_dist = -int(1e9)
    for i in range(2, n+1):
        if distance[i] != int(1e9) and max_dist <= distance[i]:
            max_dist = distance[i]
            
    for i in range(2, n+1):
        if distance[i] == max_dist:
            answer += 1
    return answer

Lv 3. 순위

풀이

2등에게 이기면 1등, n-1등에게 지면 꼴등이라는 것에 집중하면 안된다...^^ 이 문제는 플로이드 워셜로 접근해야한다.
플로이드 워셜 위에서 바로 공부해놓고 직접 문제에는 대입 못하는 거 조금 눈물난다.

a가 k에게 이기고, k가 b에게 이긴 경우, a는 b를 이긴 것이다.
a가 k에게 지고, k가 b에게 진 경우, a는 b에게 진 것이다.

위 포인트에 집중해서 풀면 된다.

참고하기 좋은 풀이 (프로그래머스 다른 사람 풀이에서 가져옴)

def solution(n, results):
    total = [['?' for i in range(n)] for j in range(n)]

    for i in range(n):
        total[i][i] = 'SELF'

    for result in results:
        total[result[0]-1][result[1]-1] = 'WIN'
        total[result[1]-1][result[0]-1] = 'LOSE'

    for k in range(n):
        for i in range(n):
            for j in range(n):
                if total[i][k] == 'WIN' and total[k][j] == 'WIN':
                    total[i][j] = 'WIN'
                elif total[i][k] == 'LOSE' and total[k][j] == 'LOSE':
                    total[i][j] = 'LOSE'

    answer = 0

    for i in total:
        if '?' not in i:
            answer += 1

    return answer

Lv 5. 방의 개수