[문제풀이] 최소신장트리와 크루스칼 알고리즘의 이해

문제 1: 거스름돈

백준 11404번을 풀어보자.

• 문제 난이도: ★★★☆☆
• 문제 유형: 최단 경로, 플로이드 워셜
• 추천 풀이 시간: 40분

풀이

이 문제는 다익스트라가 아닌 플로이드 워셜을 사용하는 문제이다.

다익스트라 vs 플로이드 워셜
(이 블로그를 참고했다.)

• 다익스트라
  • 시간 복잡도는 $O(ElogE)$
  • 하나의 정점에서 모든 정점으로 가는 최단거리를 구함.
  • 우선순위 큐 사용

        1. 시작 노드 결정 0으로 초기화 후 우선순위 큐에 담음
        2. 나머지 노드 무한대로 초기화
        3. 우선순위 큐에서 pop한 후 그 노드에서 갈 수 있는 노드를 확인
        4. 더 빠르다면 갱신하고 우선순위 큐에 넣는다.
        5. 방문했거나, 더 느리다면 continue
        6. 우선순위 큐가 빌 때까지 3-5번을 반복한다.
    

• 플로이드 워셜
  • 시간 복잡도는 $O(V^3)$
  • 모든 정점에서 모든 정점으로 가는 최단거리를 구함.
  • 그러므로 그래프는 2차원 배열
  • 가중치가 음수인 경우도 적용 가능

        1. 인접행렬을 저장할 2차원 배열을 만들고 무한대로 초기화
        2. 간선정보저장, 제자리 0으로 초기화
        3. 경유지를 기준으로, 해당 경유지를 거쳐가는게 빠르다면 갱신
    (i 가 경유지라면, A[j][k] = min(A[j][k],A[j][i]+A[i][k]) )
        4. 모든 정점을 경유지로 선정해 3번 반복
    

INF = int(1e9)

n = int(input())
m = int(input())
graph = [[INF] * (n+1) for _ in range(n+1)]

# 제자리는 0으로 초기화
for a in range(1, n+1):
    for b in range(1, n+1):
        if a==b:
            graph[a][b] = 0
            
# 각 간선에 대한 정보를 입력 받아 초기화
for _ in range(m):
    a,b,c = map(int, input().split())
    graph[a][b] = min(graph[a][b], c) # 중복되는 간선이 있기 때문에 가장 비용이 적은 간선만 고려

# 경유지를 기준으로, 해당 경유지를 거쳐가는게 빠르다면 갱신 (모든 정점을 경유지로 선정해 3번 반복)
for k in range(1, n+1):
    for a in range(1, n+1):
        for b in range(1, n+1):
            graph[a][b] = min(graph[a][b], graph[a][k]+graph[k][b])
            
# 결과값 출력
for a in range(1, n+1):
    for b in range(1, n+1):
        if graph[a][b] == 1e9:
            print(0, end=" ")
        else:
            print(graph[a][b], end=" ")
    print()

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기