기록방

👉 문제링크🔸 문제 분석 🔸1번 도시부터 다른 도시로 가는 K번째 최단 거리를 구해야 한다.K번째 최단 경로가 없으면 -1 출력한다.🔸 문제 풀이 🔸한 노드부터 다른 노드까지의 최단 거리를 구하므로, 다익스트라 (Dijkstra) 알고리즘을 선택한다.일반적인 다익스트라와 다르게, 거리를 업데이트이트 하지 않고 우선 순위 큐에 다시 넣는다.무한 순환 혹은 너무 많은 원소가 생기지 않도록, K개 까지만 거리를 구한다.🔸 코드 🔸import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.IOException;import java.io.InputStreamReader;import java.io.OutputStreamWrite..

👉 문제링크🔸 문제 분석 🔸N개의 지역과 M개의 횡단보도가 있다.횡단보도는 입력 순서대로 0~M-1 초에 파란불이 켜져 건널 수 있다.1번 지역부터 출발해 N번 지역에 도착할 수 있는 최단 시간을 출력한다.🔸 문제 풀이 🔸N이 최대 10만, M이 최대 70만이므로 BFS로 최단시간을 구하면 시간초과가 난다. 따라서 Dijkstra(다익스트라) 알고리즘을 이용해 최단시간을 구한다.현재 지역에서 갈 수 있는 다음 지역을 건널 때 걸리는 시간을 계산하고, 기록 된 소요 시간보다 작다면 업데이트한다.🔸 코드 🔸import java.io.*;import java.util.ArrayList;import java.util.PriorityQueue;import java.util.Queue;import ja..

👉 문제링크🔸 문제 분석 🔸N*M 미로에서 (1, 1) 부터 (N, M) 까지 가는 최소 비용을 구하는 문제이다.미로는 빈 방과 벽으로 이루어져 있고, 벽을 부수는데 비용이 1 소모된다.🔸 문제 풀이 🔸가중치가 0과 1로 이루어진 그래프에서 최소 비용 혹은 최단 경로를 구하는 문제라고 볼 수 있다.최단 경로 문제는 다익스트라(Dijkstra) 알고리즘을 많이 사용한다. 첫 번째 풀이에서 사용했다.다익스트라의 시간 복잡도는 O(E log V) 이다.노드를 방문해 가며, 가중치가 더 적은 경로가 발견되면 해당 노드부터 다시 경로를 탐색해보는 방법이다.가중치가 0과 1로 이루어진 경우에 0-1 BFS를 사용해서 더 효율적으로 풀이할 수 있다.0-1 BFS의 시간 복잡도는 O(V + E) 이다.모든 노..

👉 문제링크 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 🔸 문제 분석 🔸 N개의 도시와 도시 사이를 연결하는 M개의 단방향 도로가 존재한다. 도로 하나 당 1의 거리를 갖는다. X번 도시에서 시작해 최단거리가 정확히 X 거리만큼 떨어진 도시의 목록을 출력한다. 🔸 문제 풀이 🔸 하나의 노드에서 다른 모든 노드들의 최단 거리를 구해야 하므로 다익스트라 알고리즘을 사용한다. N은30만개인데, 우선순위 큐를 활용해 O(NlogN)으로 해결..

👉 문제링크 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 🔸 문제 분석 🔸 가중치가 있는 방향 그래프에서 시작 노드부터 다른 모든 노드까지의 최단 거리를 구한다. 정점의 수 V, 간선의 수 E. 시작 노드 K와 연결 정보가 주어진다. 가중치는 10 이하의 자연수이다. 다익스트라의 반복이나 프림 알고리즘으로 풀이할 수 있다. 시작 노드에서 아직 방문하지 않은 인접 노드 중 최소 가중치 간선을 선택해 탐색한다. (갈 수 있는 간선 중 최소 값을 선택하면 최단거리가 보장된다..