[백준] Python,Java로 풀기📖/최단거리

https://www.acmicpc.net/problem/4485예제 풀이일단 첨에는 DFS로 이용해서 풀었지만 아니나 다를까,, 바로 시간초과..⭐️그래서 생각한건 다익스트라 알고리즘으로 최단 경로 알고리즘이었다..예제 하나를 이용해서 다익스트라 알고리즘을 풀이하면 다음 사진과 같다고 생각하면 이해하기 쉽다. 만약 다익스트라 알고리즘이 먼가,, 이것부터라면 밑에 링크로 들어가는것을 추천한다 (나름 이코테 책보면서 정리해둔 다익스트라알고리즘이다. ) [이코테] CHAPTER 09 최단 경로 알고리즘 - 다익스트라 최단 경로 알고리즘최단 경로 알고리즘(Shortest Path) : 가장 짧은 경로를 찾는 알고리즘 1) 최단 경로 문제- 지점( 노드 ), 지점 간 연결된 도로( 간선 ) - 한 지점에서 다른..

10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net 예제 풀이 그림으로 표현하면 이런식으로 표현 된다. 그럼 연결된 노드들을 표로 표현하면 이렇게 된다 이제 차례대로 1번노드부터 6번노드까지 경로노드로 거쳐서 간다고 할 때 표를 작성하면 1️⃣ 1번 노드가 경로노드인 경우 -> 없음 2️⃣ 2번 노드가 경로노드인 경우 -> 1번 노드에서 3번 노드로 가는 경우 D13 = (D12 + D23) =2로 변경 3️⃣ 3번 노드가 경로노드인 경우 -> 1번 노드에서 4번 노드로 가는 경우 D14 ..

11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 예제 풀이 시작 도시와 도착 도시를 연결하는 노선이 하나가 아닐 수 있으므로 또 입력 받을 경우 최단 거리로 입력 받게 만든다. 그렇게 입력 받은 노드들을 출발 노드를 세로, 도착 노드를 가로로 표를 작성한다. 1 ) 1번 노드를 거처셔 표 작성 2) 2번 노드를 거쳐서 표 작성 3) 3번 노드를 거쳐서 표 작성 이런식으로 노드마다 경로노드라고 할 경우 표를 갱신해서 표현한다. 그렇게 되면 결국 밑의 표와 같이 표가 나오게 된다. 출발 \ 도착 1 2 3 4 5 ..

2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 예제 설명 최소 거리는 1 , 최대 거리는 9(arr[-1])-1(arr[0]) = 8 1) 최소 거리가 4인 경우(mid) 공유기 설치 집과 집 사이의 거리 start mid =(1+8)//2=4 end 1 2 3 4 5 6 7 8 공유기 설치 1 2 4 8 9 최소 거리가 4가 되는 경우에는 1부터 시작해서 1+4=5 이상의 좌표에 공유기를 설치해야한다. 그렇기 때문에 1에 설치 후에 5이상의 좌표인 8에 ..

참고자료 : 다익스트라 알고리즘 참고 자료 [이코테] CHAPTER 09 최단 경로 알고리즘 - 다익스트라 최단 경로 알고리즘 최단 경로 알고리즘(Shortest Path) : 가장 짧은 경로를 찾는 알고리즘 1) 최단 경로 문제- 지점( 노드 ), 지점 간 연결된 도로( 간선 ) - 한 지점에서 다른 한 지점까지의 최단 경로를 구해야 하는 경우 coooco.tistory.com 예제 설명 1번 노드에서 시작할 경우 도착 노드 1번 2번 3번 4번 최소 비용 0 3 5 4 2번 노드에서 시작할 경우 도착 노드 1번 2번 3번 4번 최소 비용 3 0 3 4 3번 노드에서 시작할 경우 도착 노드 1번 2번 3번 4번 최소 비용 5 3 0 1 1번 노드 -> 2번 노드 -> 3번 노드 -> 4번노드 인경우 최..