Dijkstra (5) 썸네일형 리스트형 [백준] 지름길(python) 백준, 지름길 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이 www.acmicpc.net TL;DR 최단 경로 찾기 - 다익스트라 알고리즘(Dijkstra algorithm) 문제 요약 1. D킬로미터의 고속도로에 존재하는 지름길을 이용했을 때 가장 짧은 거리를 출력하는 프로그램을 작성하라. - 0부터 D 킬로미터 떨어진 고속도로에서 지름길들에 대한 정보가 주어질 때 각 길을 사용했을 때 최단 거리로 목적지에 도착할 수 있는 거리를 계산하면 되는 프로그램이다. 입출력 형태 예시 1 :: 이 경우 가장 짧은 경로는 0 ~ 50.. [백준] 촌수계산(python) 백준, 촌수계산 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net TL;DR 너비 우선 탐색(BFS) 최단경로찾기 - 다익스트라 알고리즘(Dijkstra algorithm) 문제 요약 1. 여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성하라. 2. 두 사람이 친척 관계가 없는 경우는 -1을 출력해야 한다. - 각 사람들이 노드, 노드 간의 길이는 1인 그래프의 형태를 생각할 수 있다. - 주어진 두 사람(노드) 간의 거리를 계산하는.. [백준] 그대, 그머가 되어(python) 백준, 그대, 그머가 되어 TL;DR 너비 우선 탐색(BFS) 다익스트라 알고리즘(Dijkstra Algorithm) 문제 요약 1. 바꿀 수 있는 문자 간의 관계가 표현되어 있는 그래프에서 주어진 문자를 바꿀 수 있는 최소 횟수를 반환하라. 2. 문자를 바꿀 수 없는 경우에는 -1을 출력한다. - 문자를 다른 문자로 바꿀 수 있는 관계가 주어진다. - 이 관계들에서 바꾸기를 원하는 문자를 바꿀 문자로 바꾸는데 걸리는 과정의 최소 횟수를 반환하는 프로그램을 작성하면 된다. - 각 문자들을 노드로, 바꿀 수 있는 노드들 사이의 관계를 간선의 형태로 그래프로 표현할 수 있다. 이 때, 그래프는 방향성이 없는 무향 그래프이다. - 노드 사이의 관계를 표현할 때 꺽쇠''가 아닌 괄호'()'를 사용하여 표현한 것.. [백준] 특정 거리의 도시 찾기(python) 백준 온라인 저지, 특정 거리의 도시 찾기 TL;DR 다익스트라 알고리즘(Dijkstra Algorithm) 너비 우선 탐색(BFS) 문제 요약 1. 1번부터 N번까지 N개의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다. 2. 특정 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하라. 3. 최단 거리가 K인 도시를 오름차순으로 출력한다. 존재하지 않는다면 -1을 출력한다. - 1 : N개의 노드와 M개의 간선, 간선의 가중치는 1인 그래프로 생각할 수 있다. - 다익스트라 알고리즘을 사용하여 X 노드로부터 다른 노드들까지의 최단 경로를 확인한 뒤, 경로가 K인 노드들을 반환하면 될 것 같다. 입출력 형태.. [리트코드] Network Delay Time(python) 리트코드, Network Delay Time_네트워크 지연 시간 TL;DR 너비 우선 탐색(BFS) 다익스트라 알고리즘(Dijkstra Algorithm) 문제 요약 1. 1부터 n까지 노드가 있는 네트워크가 주어진다. 주어진 네트워크는 출발 노드, 도착 노드, 출발 노드로부터 도착 노드까지 걸리는 시간을 의미한다. 2. 주어진 k 노드로부터 신호를 전달한다고 했을 때 모든 n개의 노드들 도는데 걸리는 시간을 반환하라. 3. 만약 모든 노드를 순회할 수 없다면 -1을 반환하라. - 주어진 k 노드로부터 그래프에 존재하는 모든 노드를 순회할 때의 시간을 반환하면 된다. 이는 가장 k 노드로부터 가장 먼 거리의 노드까지 걸리는 시간을 반환하면 된다. - 모든 노드를 순회할 수 있다면 BFS에서 조회할 수 있.. 이전 1 다음
