다익스트라
-
알고리즘: 백준 2211번 네트워크 복구 (feat.python)알고리즘/백준(BaekJoon) 2021. 1. 15. 15:29
2211번: 네트워크 복구 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다 www.acmicpc.net import sys import heapq read = sys.stdin.readline INF = sys.maxsize N, M = map(int, read().split()) net = {i: [] for i in range(1, N+1)} for _ in range(M): A, B, C = map(int, read().split()) net[A].append([C, B]) net[B].append([C, A]) times =[[0..
-
알고리즘: 백준 11779번 최소비용 구하기2 (feat.python)알고리즘/백준(BaekJoon) 2021. 1. 15. 13:29
11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net import sys import heapq read = sys.stdin.readline n = int(read()) m = int(read()) graph = {i:[] for i in range(1, n+1)} for _ in range(m): s, e, w = map(int, read().split()) graph[s].append([w, e]) start, end = map(int, read().split()) INF = s..
-
알고리즘: 백준 1504번 특정한 최단 경로 (feat. python)알고리즘/백준(BaekJoon) 2021. 1. 12. 14:41
1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net import sys import heapq read = sys.stdin.readline N, E = map(int, read().split()) graph = {i:[] for i in range(1, N+1)} for _ in range(E): a, b, c = map(int, read().split()) graph[a].append([b,c]) graph[b].append([a,c]) v1, v2 = map(in..
-
알고리즘: 백준 1238번 파티 (feat. python)알고리즘/백준(BaekJoon) 2021. 1. 11. 20:07
1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net import sys import heapq read = sys.stdin.readline N, M, X = map(int, read().split()) graph = {i: []for i in range(1, N+1)} # 각 마을에서 X로 가는 방향 그래프 graph2 = {i: []for i in range(1, N+1)} # X에서 각 마을로 가는 그래프 for _ in range(M): s, e, l = map(int, re..
-
알고리즘: 백준 1261번 알고스팟 (feat.python)알고리즘/백준(BaekJoon) 2021. 1. 11. 18:03
1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net import sys import heapq read = sys.stdin.readline m, n = map(int, read().split()) maze = [list(map(int,read().strip()))for i in range(n)] visit = [[0 for _ in range(m)] for _ in range(n)] def dijkstra(): dx = [1, -1, 0, 0] dy = [0, 0, 1, -1] hq = [..
-
알고리즘: 백준 1753번 최단경로 (feat.python)알고리즘/백준(BaekJoon) 2021. 1. 11. 15:25
1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net import sys import heapq read = sys.stdin.readline N = int(read()) M = int(read()) graph = {i:[] for i in range(1, N+1)} for i in range(1, M+1): s, e, v = map(int, read().split()) graph[s].append([e,v]) start, end = map(int, read().split()) INF =..
-
네트워크: Network layer 정리3(routing algorithm, link state, distance vector)네트워크 2020. 10. 30. 21:25
네트워크: Network Layer 정리2(IPv4, DHCP, NAT, SDN...) 전송계층에서는 segment라는 패킷단위를 다루었다면 네트워크 계층" data-og-host="seungjuitmemo.tistory.com" data-og-source-url="https://seungjuitmemo.tistory.com/94" data-og-url="https://seungjuitmemo... seungjuitmemo.tistory.com 저번 포스팅에 이어 Network layer control plane에서 routing 프로토콜에 대해서 알아본다. 이번 포스팅은 효율적인 라우팅 알고리즘을 만들기 위해 어떤 알고리즘을 사용하는지가 주내용이다. 우선 라우팅 프로토콜에 대해서 알아보기 전, cont..