본문 바로가기

다익스트라4

0-1 BFS 0-1 BFS란? 💡 0-1 BFS 가중치가 0 또는 1로만 주어진 그래프에서, 시작 노드가 주어졌을 때 다른 모든 노드로의 최단 경로를 찾고자 할 때 사용하는, BFS를 응용한 알고리즘이다. 보편적으로 그래프에서 최단 경로를 찾을 때 사용하는 다익스트라 알고리즘의 경우, 시간 복잡도가 O(ElogV)인 반면, 0-1 BFS의 시간 복잡도는 O(V + E)로 선형 시간에 해결할 수 있는 효율적인 알고리즘이다. 다익스트라에 대해 알고 싶다면 다음 링크를 참조하면 좋을 것 같다. 다익스트라, Dijkstra Algorithm 코딩 문제에서 많이 볼 수 있는 그래프와 관련된 알고리즘을 공부해보자. 그래프에서 최단 거리를 구하는 알고리즘은 다음과 같은 것들이 있다. 💡 그래프의 최단 거리 구하는 알고리즘 1. .. 2024. 1. 22.
BOJ G4 1504 특정한 최단 경로 JAVA 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 문제 읽기 방향성이 없는 그래프가 주어진다. 양방향이어도 다익스트라를 사용하는 데에는 전혀 문제가 없고, 단지 처음에 그래프를 인접 리스트로 입력 받을 때, 양 쪽에 다 넣어주면 된다. 일단 이 문제에서는 주어지는 두 노드를 반드시 방문하면서 1 → N까지의 최소 거리를 구해야 한다. 즉, 주어지는 두 노드를 mid1, mid2라고 한다면, 1 → mid1 → mid2 → N 또는 1 → mid2 → mid1 → N .. 2024. 1. 21.
BOJ G5 1916 최소비용구하기 JAVA 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 문제 읽기 어제 공부했던 다익스트라 문제이다. 연습 삼에 몇 문제 정도 더 풀어보려고 한다. 다익스트라 개념과 동작 과정을 이해하고 싶으면 다음 포스팅을 참고하면 좋다! 다익스트라, Dijkstra Algorithm 코딩 문제에서 많이 볼 수 있는 그래프와 관련된 알고리즘을 공부해보자. 그래프에서 최단 거리를 구하는 알고리즘은 다음과 같은 것들이 있다. 💡 그래프의 최단 거리 구하는 알고리즘 1. 다익 rue-mi.tistory.. 2024. 1. 20.
다익스트라, Dijkstra Algorithm 코딩 문제에서 많이 볼 수 있는 그래프와 관련된 알고리즘을 공부해보자. 그래프에서 최단 거리를 구하는 알고리즘은 다음과 같은 것들이 있다. 💡 그래프의 최단 거리 구하는 알고리즘 1. 다익스트라, Dijkstra 2. 벨만-포드, Bellman-Ford 3. 플로이드-와샬, Floyd-Wrasahll 그 중에서 가장 많이 쓰이는 다익스트라에 대해 먼저 알아보자! 다익스트라 알고리즘, Dijkstra Algorithm 💡 다익스트라, Dijkstra 그래프의 최단 경로를 구하는 알고리즘 중 하나로, 하나의 정점에서 다른 모든 노드까지의 최단 거리를 구할 수 있는 알고리즘이다. 단, 음수 가중치는 없어야 한다. (음수 가중치가 있다면 벨만 포드 사용) [시간복잡도] V : 노드의 숫자, E : 간선의 숫자 .. 2024. 1. 20.

티스토리툴바