출처: 이것이 취업을 위한 코딩 테스트다 with 파이썬, Q 38, p 386 플로이드 워샬 알고리즘을 활용해 풀이했습니다. 현재 학생을 제외한 나머지 학생들이 현재 학생보다 성적이 낮은지, 높은지 모두 알면 그 학생의 정확한 순위를 알 수 있습니다. A번 학생의 성적이 B번 학생보다 낮다면 화살표가 A에서 B를 가리키도록 하면, 플로이드 워샬 알고리즘 수행 후 그래프의 n번째 가로줄(행)에 INF가 아닌 숫자가 있으면 그 인덱스의 학생은 n번째 학생보다 성적이 높다는 의미입니다. n번째 세로줄(열)에 INF가 아닌 숫자가 있으면, 그 인덱스의 학생은 n번째 학생보다 성적이 낮다는 의미입니다. 따라서 n번째 행과 열에서 INF가 아닌 값을 가지는 인덱스 + 자기 자신의 인덱스(n)을 합쳤을 때, 1 ~..

https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 2가지 수정사항을 제외하고 플로이드 워셜 구현 코드를 그대로 활용했습니다. (1) 시작 도시와 도착 도시를 연결하는 노선이 여러 개일 수 있다고 했으므로, 여러 개의 노선 중 최솟값만 저장하도록 수정해주었고, (2) 마지막에 결과를 프린트할 때 INFINITY 대신 0을 프린트하도록 수정했습니다. import sys INF = int(1e9) # 입력 받아오기 inputs = list(map(in..

1. (개선된) 다익스트라 알고리즘 - 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우 - 각 노드에 대한 현재까지의 최단 거리를 계속 갱신 import heapq import sys INF = int(1e9) # n: 노드의 개수 # m: 간선의 개수 # start: 시작 노드의 번호 # 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트 초기화 graph = [[] for i in range(n+1)] # 최단 거리 테이블을 모두 무한으로 초기화 distance = [INF] * (n+1) # a, b, c: a번 노드에서 b번 노드로 가는 비용이 c for _ in range(m): graph[a].append((b,c)) def dijkstra(start): q = [] # ..