[ 알고리즘 ]/Shortest Path

[백준] 11404. 플로이드

📌문제 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 🎖️난이도 ✔️풀이 import sys input = sys.stdin.readline INF = int(1e9) n = int(input()) m = int(input()) graph = [[INF]*(n+1) for _ in range(n+1)] for i in range(1, n+1): graph[i][i] = 0 for _ in range(m): a, b, c = map(int, input().split()) graph[a][b] = min(c, g..

[백준] 11403. 경로 찾기

📌문제 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 🎖️난이도 ✔️풀이 # sol1) graph[i][i]도 못간다고 생각하고 무한으로 초기화 & 플로이드워셜로 최단거리 구하기 import sys input = sys.stdin.readline n = int(input()) INF = int(1e9) graph = [list(map(int, input().split())) for _ in range(n)] for i in range(n): for j in range(n): if graph[i][j] == 0: graph[i][j] = INF # 무한..

[백준] 1753. 최단경로

📌문제 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 🎖️난이도 ✔️풀이 # 다익스트라 & 인접리스트 => sigle source, 양수 간선 존재 import heapq import sys input = sys.stdin.readline # 안해주면 시간초과 INF = int(1e9) v, e = map(int, input().split()) start = int(input()) graph = {i : [] for i in range(1, v+1)} dist = [IN..

[백준] 18352. 특정 거리의 도시 찾기

📌문제 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 🎖️난이도 ✔️풀이 # bfs & 인접리스트 from collections import deque import sys input = sys.stdin.readline # 안해주면 시간초과 # 도시개수(n), 도로개수(m), 거리정보(k), 출발도시번호(x: single source) n, m, k, x = map(int, input().split()) graph = {i:[] for ..

[개념 정리] 최단 경로 (Shortest Path) 알고리즘

[220711][스터디준비] - 최단경로 최단 경로(Shortest Path) 알고리즘이란? wise-soybean-8bd.notion.site