728x90 반응형 알고리즘6 Dijkstra - 데이크스트라(다익스트라) 데이크스트라(Dijkstra)는 BFS 알고리즘을 알고 있다면 조금 더 쉽게 이해할 수 있다. 시작 지점 부터 가고자하는 도착지점까지 최소한의 시간으로 도착할 수 있는 거리를 구하는 알고리즘이다. ex)https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 예제 입력은 1번에서 출발하여 5번까지 도착하는데 걸리는 최소 시간을 구하는 문제입니다. 1 -> 4 -> 5을 이동하게 된다면 1 + 3 = 4의 시간이 걸리게 .. 2023. 1. 22. BFS - 너비 우선 탐색 / DFS - 깊이 우선 탐색 너비 우선 탐색(Breadth First Search) / DFS(Depth First Search)은 시작지점부터 갈 수 있는 지점들을 들리면서, 더이상 갈 곳이 없을때까지 반복한 후 종료한다. ex) https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 해당 문제는 이런 모양의 간선과 노드들로 이루어져 있습니다. 1번 컴퓨터에 바이러스가 걸리게 된다면, 1과 2, 3, 5, 6 총 4개의 컴퓨터가 1번 컴퓨터에 의해 바이러스에 감염되면서, 5개의 컴퓨.. 2023. 1. 22. 이전 1 2 다음 728x90 반응형
