기록방

👉 문제링크🔸 문제 분석 🔸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)으로 해결..

👉 문제링크 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 🔸 문제 분석 🔸 n개의 노드와 m개의 단방향 간선 정보가 주어진다. 시작 노드부터 목적지 노드까지의 경로 중 비용이 최소값이 되는 경로를 찾아, 비용과 경로 상의 노드 수 및 경로를 출력한다. 같은 최소값이면서 다른 경로일 수 있는데, 모두 정답으로 인정된다. 🔸 문제 풀이 🔸 다익스트라 알고리즘으로 최단경로를 구한다. 비용의 최소값 뿐만 아니라 최단경로를 출력해야 하므로, 값이 경신될 때 이전 출발 노드의 번호를 저..

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

👉 문제링크 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 🔸 문제 분석 🔸 N개의 노드와 E개의 간선이 있다. 1번 노드부터 N번 노드까지의 최단거리를 구하는데 v1과 v2 노드를 경유해야 한다. 다익스트라 알고리즘의 활용으로 풀이 가능하다. (난 프림 알고리즘으로 생각했다) 경로는 2가지 종류가 있다. (1 > A > B > N , 1 > B > A > N) 첫 번째 경우는 1 > A, A > B, B > N 의 최단거리를 각각 구해야 한다. 두 번째 경우는 ..