다익스트라 알고리즘5 [백준 13549] 숨바꼭질3 / 자바 / 다익스트라 알고리즘 #문제 레벨: G5알고리즘: BFS(그래프 탐색) 풀이시간: 30분힌트 참조 유무:https://www.acmicpc.net/problem/13549#문제 풀이 직관적으로 가장 빠른 방법은 -초를 소비하고 2배를 가는 거다. 그렇다면 우린 다익스트라 알고리즘을 사용하면 된다. 최종 목표지까지 최소한의 비용을 알고싶다면 출발지부터 최소한의 비용의 노드들 부터 탐색하면 되는 거다. 그래서 미리 큐에 거듭해서 거리는 두배지만 시간은 그대로인 배열이 거듭해서 추가 되고 먼저 빼지는 거다.#풀이 코드 import java.util.*;public class Main { static final int MAX = 100001; public static void main(.. 2024. 9. 14. [백준 28707] 배열 정렬 / 자바 / 다익스트라 알고리즘 #문제 레벨: G1알고리즘: 다익스트라 알고리즘풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/28707 #문제 풀이 이 문제는 다익스트라 알고리즘을 사용한다. 통상적인 다익스트라 알고리즘은 노드에 도입하여 이 문제에 대해서 어떻게 다익스트라 알고리즘을 이용할지 가늠이 안 갈 수도있다. 다익스트라 알고리즘을 적용할 때 노드가 아니라 상태A -> 상태 B로 갈 때 최소 비용이라고 생각하면 이해하기 편할 거다. 만약 예제2번을 들어 설명하자면,1313 - > 1133 로 갈 때의 최소비용을 저장하는 것이다. 다익스트라 알고리즘을 사용할 수 있는데 또 다른 이유가 있다. 당연한 이야기지만, 우리는 정렬된 정답 배열을 알고있다. 만약 131.. 2024. 9. 11. [프로그래머스 LV3] 스킬 체크 / 자바 / 다익스트라 알고리즘 문제 레벨: Lv3알고리즘: 다익스트라 알고리즘 풀이시간: 1시간힌트 참조 유무: 유1 번째 시도 [알고리즘 설명]다익스트라 알고리즘으로 S를 기준으로, A를 기준으로, B를 기준으로 각각의 노드의 최소거리르 구해야 한다.그리하여출발점 -> A,B가 찢어지는 노드 -> 찢어지고 A가 가는 거리, 찢어지고 B가 가는 거리출발점 -> A가 가는 거리 + 출발점 -> B가 가는 거리 두 가지 경우를 다 고려할 수 있다. import java.util.*;class Solution { public int solution(int n, int s, int a, int b, int[][] fares) { List> graph = new ArrayList(); for .. 2024. 7. 2. [백준] 최단경로 / 자바 문제 레벨: G4알고리즘: 다익스트라 풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/17531 번째 시도 [다익스트라 알고리즘에서 우선순위 큐를 쓰는 이유]최소거리 값 갱신 횟수의 감소때문이다. 먼저 우선순위 큐를 쓰지 않고 일반 큐를 써도 결과에는 차이가 없다. 하지만 우선순위 큐를 쓰는 이유는 속도에 이점이 있기 때문이다.import java.io.*;import java.util.*;class Node implements Comparable{ int end, weight; public Node(int end, int weight){ this.end = end; this.weight = weight;.. 2024. 5. 28. [백준] 파티 / 자바 문제 레벨: G3알고리즘: BFS풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/1238 1 번째 시도: 실패 가중치가 있기 때문에 인접리스트 대신 인접행렬 선택갈 때 최단 거리를 구하는 dfs와 돌아올 때 최단 거리를 구하는 dfs2왜 굳이 dfs를 두개로 나누었나? 현 코드 dfs 리턴 값은 void로 답을 전역변수에 할당했다.효율적인건 리턴 값을 int로 하여 전역변수를 사용하지 않는 거다그러나 구현에 어려움이 있어 답을 전역변수에 할당하고 dfs를 2개로 나뉘었다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import .. 2024. 5. 27. 이전 1 다음
