반응형 알고리즘/다익스트라10 백준 2211번 : 네트워크 복구 java 이 문제는 다익스트라 알고리즘을 이용하여 1번 컴퓨터에서 각 컴퓨터로 향하는 최단 경로를 구하고 그 경로를 출력하는 문제입니다. 저는 이를 위하여 PriorityQueue 안에 각각의 노드에는 목표 정점(to)과 그 정점으로 가기 직전의 정점(from), 시작 정점에서 목표 정점까지의 거리(val)를 저장하였습니다. 그리고 각 정점에 처음 방문하였을 때 to와 from을 다른 ArrayList에 담아 최단 경로를 저장하였습니다. import java.io.*; import java.util.*; public class Main { static int N; static List l = new ArrayList(); static List answer = new ArrayList(); public static.. 2022. 7. 27. 백준 1719번 : 택배 java 이 문제는 각각의 번호마다 다익스트라 알고리즘을 적용하여 각각의 정점마다 다른 정점까지 갈 때의 최단경로에서 처음으로 거쳐가는 정점을 출력하는 문제입니다. 저는 최단 경로에서 처음 거쳐가는 정점을 구하기 위해서 firstGo라는 배열을 따로 만들어서 이 정점에 오기 위해서 처음 거쳐야 하는 정점을 저장하게 만들었습니다. 이 firstGo라는 배열은 초기값으로 자기 자신의 정점 번호를 가지고 있습니다. 그리고 시작 정점에서 다른 정점을 거쳐서 자신의 정점으로 오는 것이 더 효율적이라면 firstGo 배열에서 그 정점의 인덱스에 저장되어 있는 정점을 저장하게 하는 식으로 최단 경로에서 처음 간 정점을 구하게 만들었습니다. 위의 그림과 같은 그래프가 있다고 가정하겠습니다. 이 그래프를 이용하여 다익스트라 알고.. 2022. 7. 23. 백준 5972번 : 택배 배송 java 이 문제는 다익스트라 알고리즘을 이용하는 기초 문제입니다. 다익스트라 알고리즘에 대한 설명은 아래의 링크에 있습니다. 백준 1753번 : 최단경로 java 이 문제는 다익스트라 알고리즘을 푸는 문제입니다. 이 문제를 풀 때 유의하셔야 하는 점은 메모리 제한이 256MB라는 점입니다. 저는 이 문제를 풀 때 처음에는 들어온 자료들을 2차원 배열에 입 dy-coding.tistory.com import java.io.*; import java.util.*; public class Main { static int N; static List l = new ArrayList(); static int[] dist; public static void main(String[] args) throws IOExceptio.. 2022. 7. 22. 백준 4485번 : 녹색 옷 입은 애가 젤다지? java 이 문제는 다익스트라 알고리즘을 이용하여 (0, 0)에서 (N-1, N-1)까지 갈 때까지 최소한으로 소지금을 잃으면 서 갈 수 있는 경로를 찾는 문제입니다. 우선 (0, 0)에서 시작하여 주변 정점들의 비용을 확인하면서 더 비용이 적게 드는 경로를 선택하여 진행하면 됩니다. import java.io.*; import java.util.*; public class Main { static int[] dR = {1, -1, 0, 0}; static int[] dC = {0, 0, 1, -1}; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader.. 2022. 7. 21. 백준 10282번 : 해킹 java 이 문제는 다익스트라 알고리즘을 이용하여 시작 정점에서 시작되어 컴퓨터가 감염되는 시간과 몇 대가 감염되었는지 출력하는 문제입니다. 이 문제에서는 테스트 케이스마다 컴퓨터간의 의존성 관계를 입력받은 후 다익스트라 알고리즘을 각각 실행하여 어느 컴퓨터까지 감염되었는지 확인합니다. 다익스트라 알고리즘을 활용할 줄 알면 조건에 따라 쉽게 해결할 수 있는 문제입니다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); Stri.. 2022. 7. 15. 백준 1504번 : 특정한 최단 경로 java 이 문제는 다익스트라 알고리즘을 이용하여 중간에 정점 v1과 v2를 거쳐 N으로 갈 때의 최단 경로의 길이를 구하는 문제입니다. 이 문제를 풀기 위해서는 우선 정점 1에서 v1과 v2로 갈 때의 최단 경로의 길이를 구해야 합니다. 만약 경로가 존재하지 않을 경우에는 그다음 단계를 진행하지 않아도 됩니다. 1에서 v1으로 가는 경로가 없다고 가정하면 1에서 v2로 가는 최단 경로를 구하고 그 후 v2에서 v1으로 가는 최단 경로를 구해야 합니다. v2와 v1을 모두 거쳐야 하기 때문에 이 경로를 구해줍니다. 그리고 마지막으로 v1에서 N으로 가는 최단 경로를 구한 후 이 3개의 경로의 길이를 더한 값을 출력합니다. 이에 대해서 예제 1번을 예시로 설명드리겠습니다. 위 그림은 예제 1번을 나타낸 그림입니다... 2022. 6. 25. 백준 1238번 : 파티 java 이 문제는 다익스트라 알고리즘을 이용하여 학생들이 파티를 참가하기 위해 한 마을로 모였다가 다시 자신의 마을로 돌아갈 때 가장 시간이 오래 걸리는 학생의 소요시간을 구하는 문제입니다. 이 문제를 푸는 방법은 2가지가 있습니다. 우선 첫 번째의 방법은 플로이드 와샬 알고리즘을 이용하여 각각의 학생들이 오고 갈 때의 시간을 구하는 방법이 있습니다. 하지만 이 방법을 사용한다면 시간 복잡도가 O(n^3)이 되어 시간이 오래 걸리게 됩니다. 이 문제에서는 플로이드 와샬 알고리즘을 써도 맞다고는 나오지만 N이 더 늘어나면 시간이 메모리를 더 많이 쓰게 되므로 좋은 정답이 아닙니다. 우선 플로이드 와샬 알고리즘으로 이 문제를 풀었을 때를 보여드리겠습니다. import java.io.*; import java.uti.. 2022. 6. 24. 백준 14938번 : 서강그라운드 java 이 문제는 다익스트라 알고리즘을 이용하여 탐색하는 알고리즘입니다. 저는 이 문제를 처음 봤을 때 bfs로도 풀 수 있을 것 같았습니다. 그래서 bfs로 문제를 먼저 풀어보았는데 bfs로 문제를 풀 때 탐색하지 않는 부분이 있을 수 있다는 것을 알게 되었습니다. 위의 그림과 같이 그래프가 존재할 때 bfs로 이 문제를 풀면 A -> B 경로를 탐색한 후 바로 A -> C 경로를 탐색합니다. 수색 범위가 10이라고 했을 때 A->C를 통해 C 노드에 이미 접근했기 때문에 A -> B -> C 경로가 더 짧음에도 불구하고 경로가 새로 생성되지 않습니다. 따라서 A -> B -> C -> D 경로로 가면 총 거리가 6이기 때문에 탐색할 수 있는 노드이지만 bfs를 이용하면 탐색할 수 없게 됩니다. 따라서 다익스.. 2022. 6. 11. 이전 1 2 다음 반응형
