https://www.acmicpc.net/problem/9370   📌 자바(Java)로 푸는 미확인 도착지 문제 - 백준 9370 🚗📍 🔎 문제 개요 백준 9370번 - 미확인 도착지 문제입니다.출발지(S)에서 목적지 후보들 중,특정 도로(G-H)를 반드시 지나면서 도달할 수 있는 목적지를 찾아야 합니다.다익스트라 알고리즘을 활용하여 최단 경로를 구하는 문제입니다. 💡 예제 입력26 9 21 2 31 2 11 3 22 3 23 4 33 5 54 5 44 6 15 6 256💡 예제 출력65 6➡ 목적지 후보 중 특정 도로(G-H)를 지나면서 도달할 수 있는 곳을 출력 🛠 알고리즘 접근 방식 이 문제를 해결하기 위해 다익스트라 최단 경로 알고리즘(Dijkstra) 을 활용합니다. ✏️ 주요 ..

BFS를 돌리되 우선순위 Q를 사용하여 4방탐색 을 하는 문제였다. BFS인 관계로 무한루프에 빠지지 않기 위해서 isVisited 로 경로를 체크하였고 우선순위 Q에서는 comparable을 이용하여 가장 마지막에 도착할시, q가 다떨어질 시 에 BFS를 종료하도록 설계하였다. package BOJ; import java.io.*; import java.util.*; class Node implements Comparable{ int x; int y; int cnt; public Node(int x, int y, int cnt) { this.x = x; this.y = y; this.cnt = cnt; } @Override public int compareTo(Node o) { if(this.cnt==..

다익스트라 문제에 다가 자료구조 한두개를 더 추가하여 다익스트라 로 경유한 정점과 정점의 갯수를 출력하는 문제였다. package algorithm.src.minho; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.PriorityQueue; import java.util.StringTokenizer; class Node implements Comparable{ int end; int val; public Node(int end, int val) { super(); this.end = end; this.val..

별것없는 다익스트라 문제지만 다익스트라 알고리즘을 해결법을 보지않고 혼자 스스로 기억을 짜내어 구현하다 보니 isVisited를 빠트려 시간초과가여러번 났던 문제.. package BOJ; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.PriorityQueue; import java.util.StringTokenizer; class Node implements Comparable{ int end; long val; public Node(int end, long val) { this.end = end; thi..

전형적인 데이크 스트라 (다익스트라) 문제 출발지에서 경유지1 경유지1에서 경유지2 경유지2에서 도착지 의 다익스트라 결과값의 합과 출발지에서 경유지2 경유지2에서 경유지1 경유지1에서 도착지 의 다익스트라 결과값의 합중 최솟값을 비교하여 풀어보았다. package algorithm.src.minho; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.PriorityQueue; import java.util.StringTokenizer; class Node imple..

다익스트라 응용 문제 package BOJ; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.PriorityQueue; import java.util.StringTokenizer; class Node implements Comparable{ int end, val; public Node(int end, int val) { super(); this.end = end; this.val = val; } @Override public int compareTo(Node o)..

대표적인 다익스트라 문제 1. list를 사용하여 간선저장(간선리스트) 2. priority queue 를 사용하여 간선 cost 낮은순 자동정렬 저장 및 visited 체크 3. dist로 1번집에서 다른집으로 갈때의 최소 cost 누적 비교 저장 4. dist[N] 이 답이다. package BOJ; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.PriorityQueue; import java.util.StringTokenizer; class Node impl..

지름길은 dijkstra 개념이 들어간 문제였다. DP와 비슷하다고 느꼈다. package BOJ; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.PriorityQueue; import java.util.StringTokenizer; class Road implements Comparable { int start; int end; int val; public Road(int start, int end, int val) { this.start = start; this.end = end; this.val = val;..

다익스트라 연습에 좋은 문제이다. 모처럼 다익스트라에 약했던 내게 딱 좋은 문제였다. package BOJ; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.PriorityQueue; import java.util.StringTokenizer; class Node implements Comparable{ int end; int val; public Node(int end, int val) { super(); this.end = end; this.val = val; ..

다익스트라의 개념을 알수 있는 문제다. 다익스트라는 BFS에서 Queue를 사용하지만 Compareable과 priority queue를 사용하여 BFS 처럼 모든 경우를 보는 것이 아닌 가중치가 최저인 값을 우선적으로 확인한다. 고로 BFS보다 빠른 것으로 나타난다. 음의 가중치일때는 사용할 수 없으며 출발점과 도착점이 정해진 경우에 사용가능한 다익스트라 알고리즘 이었다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.PriorityQueue; import java.util.StringTokenizer; public class b4485{ static c..