반응형 Dijikstra4 [백준/C++] 최소비용 구하기 2 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 예전에 풀었던, 최단거리 알고리즘과 같은 문제다.그래서 N이 1000이고 E가 100,000이므로 우선순위 queue를 이용한 dijikstra로 문제를 풀었다. 들어온 경로들로 graph를 만들고, 시작점부터 시작해 위치, 비용의 정보를 가진 pair를 priority queue에 넣는다.이후 가장 비용이 적은 위치의 값을 가져와 다시 pq에 넣는 과정을 반복하면 된다.여기서 최소 비용과 어느 도시에서 왔는지 정보를 저장할 visited라는 이름의 vector> 를 만들어 관리한다. 이후 pq에서 도시를 .. 2024. 5. 13. [백준/C++] 미확인 도착지 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 특정 시작점 st에서 도착점 ed로 가는 최단 경로에 임의의 두 점 (m, n)을 잇는 경로가 포함되어 있는지 계산하는 문제다. 문제를 해결하는 방법은 여러 방법이 있다. 1. Dijikstra 알고리즘으로 두 점 m, n을 잇는 경로를 포함하는지 체크한다. 2. Dijikstra 알고리즘으로 최단경로와 [st -> m -> n -> ed, st -> n -> m -> ed]의 최단 경로의 길이가 같은지 비교하는 방법이 있다. 이 중에서 1번 방법으로 코드를 구현해 문제를 풀었다. Dijikstra 알고리즘과 동일하게 코드를 구현하지만 m, n을 잇는 경로를 포함하는지 체크할 배열을 하나 만든다. 이후.. 2024. 4. 17. [백준/C++] 특정한 최단 경로 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 중간에 반드시 두 정점을 거쳐서 가는 최단경로를 찾는 문제다. 결국 최단경로를 찾는 문제기 때문에 Dijikstra 알고리즘으로 쉽게 풀 수 있다. 제한사항을 보면 V의 개수가 최대 800이기 때문에 O(N^2)의 시간복잡도로 문제를 풀어도 빠르게 풀 수 있는 문제다. 이 문제의 특징은 양방향 간선이기 때문에 a -> b의 최단거리는 b -> a의 최단거리와 같다. 그러므로 이를 이용하면 최단거리를 구하기 위해서는 두 개의 값만 비교하면 된다. 1. 1 -> a -> b -> V로 도착하는 경우 2. 1 -> b -> a -> V로 도착하는 경우 위의 두 경우를 비교하면 되는데, a -> b의 최단거리.. 2024. 4. 16. [백준/C++]최단경로 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 특정 시작점에서 다른 정점에 도착하는 최단 경로를 구하는 문제다. 최단 경로를 구하는 알고리즘에는 다익스트라(Dijikstra) 알고리즘이 있다. 다익스트라 알고리즘은 아래 순서로 진행된다. 1. 방문하지 않은 정점 중에서 가장 비용이 적은 방문할 수 있는 정점을 선택한다. 2. 선택한 정점에서 이동할 수 있는 정점들을 방문할 수 있는 정점에 추가하고, 이동했을 때 드는 비용을 갱신한다. 3. 선택한 정점을 방문처리하고, 다시 1번 과정을 반복한다. 이 과정에서 가장 비용이 적은 방문할 수 있는 정점을 선택하는 방법에 따라 시간복잡도가 달라진다. 만약 V개의 노드를 전부 탐색할 경우 O(V^2)의 시간.. 2024. 4. 15. 이전 1 다음 반응형