본문 바로가기

728x90

알고리즘 문제 풀이/Shortest Path6

[백준]1753번: 최단경로 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 모든 간선의 가중치가 자연수로 주어졌으므로, 다익스트라 알고리즘을 사용할 수 있다. 입력값으로 주어지는 정점의 개수와 간선의 수가 매우 많으므로 시간복잡도가 낮은 우선순위큐를 활용하여 구현했다. https://catromi.tistory.com/65 다익스트라 알고리즘 구현 (python) 다익스트라 알고리즘 (Dijkstra Algorithm) -특정 노드에.. 2023. 2. 28.

[백준]18352번: 특정 거리의 도시 찾기 https://www.acmicpc.net/problem/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 다익스트라 import sys import heapq input = sys.stdin.readline INF=int(1e9) n, m, k, x = map(int,input().split()) graph=[[] for _ in range(n+1)] distance=[INF]*(n+1) for _ in range(m): a, .. 2023. 2. 28.

Floyd-Warshall 알고리즘 구현(python) Floyd-Warshall 알고리즘 -최단 경로를 찾는 알고리즘 -매 단계마다 거쳐가는 노드 k를 기준으로 최단경로를 계산한다 -즉, a->b로 가는 최단거리와 k를 거쳐 가는 a->k->b의 최단거리를 비교하여 테이블을 갱신한다. -2차원 테이블에 최단 거리 정보를 저장한다 (dp임) 구현 방법 1) 최단거리 테이블을 초기화한다. (각 노드에서 인접한 다음 노드로 가는 데 드는 비용을 기록) 2) 각 노드를 거쳐 가는 경우를 고려하며 테이블을 갱신한다. 파이썬 코드 import sys input = sys.stdin.readline INF = int(1e9) #매우 큰 숫자인 10억을 무한대로 정의한다 #n(노드 수), m(간선 수) 입력받기 n,m = map(int,input().split()) #최.. 2023. 2. 28.

다익스트라 알고리즘 구현 (python) 다익스트라 알고리즘 (Dijkstra Algorithm) -특정 노드에서 출발하여 다른 모든 노드까지 갈 수 있는 최단경로를 계산 -매 상황에서 가장 비용이 적게 드는 노드를 선택하는 과정을 반복한다 (그리디임) -모든 간선의 가중치가 양수일 때 정상적으로 동작한다 구현 방법 1) 최단거리 테이블을 초기화한다. (출발노드는 0, 나머지는 INF) 2) 현재 노드와 인접하고 방문하지 않은 노드 중 최단거리가 가장 짧은 노드를 선택 3) 2에서 선택한 노드를 거쳐 다른 노드로 가는 비용을 계산, 최단거리 테이블을 갱신 4) 2,3번 과정 반복 현재 노드로부터 최단거리가 가장 짧은 노드 선택하기 간단하게 인접한 노드를 매번 모두 순회하는 방법을 떠올릴 수 있다. 그러나 선형탐색으로 최단거리가 짧은 노드를 선택.. 2023. 2. 28.

[이코테]미래 도시 Floyd-Warshall 알고리즘으로 노드간 최단경로 구한다 1~k까지 최단거리 + k~x까지 최단거리 구한다 import sys input = sys.stdin.readline INF = int(1e9) n, m = map(int, input().split()) graph=[[INF]*(n+1) for _ in range(n+1)] 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): x,y = map(int,input().split()) graph[x][y]=1 graph[y][x]=1 x, k = map(int,input().split()) for k in range(1,n+1): for i i.. 2023. 2. 27.

[이코테]전보 출처: 이것이 취업을 위한 코딩테스트다 with 파이썬 https://www.youtube.com/watch?v=acqm9mM1P6o&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=7 문제 어떤 나라에는 N개의 도시가 있다. 그리고 각 도시는 보내고자 하는 메시지가 있는 경우, 다른 도시로 전보를 보내서 다른 도시로 해당 메시지를 전송할 수 있다. 하지만 X라는 도시에서 Y라느 ㄴ도시로 전보를 보내고자 한다면, 도시 X에서 Y로 향하는 통로가 설치되어 있어야 한다. 예를 들어 X에서 Y로 향하는 통로는 있지만, Y에서 X로 향하는 통로가 없다면 Y는 X로 메시지를 보낼 수 없다. 또한 통로를 거쳐 메시지를 보낼 때는 일정 시간이 소요된다. 어느 날 C라는 도시에서 위급.. 2023. 2. 27.

이전 1 다음

728x90

티스토리툴바