전형적인 다익스트라 문제 였따. 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 implements Comparable{ int end; int val; public Node(int end, int val) { super(); this.end = end; this.val = val; } @Override pu..

전형적인 데이크 스트라 (다익스트라) 문제 출발지에서 경유지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.Arrays; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseI..

다익스트라 응용 문제 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 문제였다. *2를 할때는 cnt를 증가시키지않고 푸는것이 핵심 package Boj; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class Main { static int min = Integer.MAX_VALUE; static int n, k; static boolean[] visited; static int max = 100000; public static class Node { int x; int t..

BFS의 틀을 깨어주는 문제였다. 보통 나 같은 초보자는 BFS든 DFS든 하나의 공식이 정해져있고 그 공식을 벗어나는걸 힘들어 한다. 하지만 이문제로 인해서 3차원배열로 Visited체크하는것과 qsize를 만들어주는것 모두 하나의 방법일 뿐 공식이 아닐수 있다는 것을 깨닫게 되었다. package BOJ; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.Queue; import java.util.StringTokenizer; class Locate { int x, y, cnt, wall; public L..

이름에서 알수 있듯이 위 문제는 플로이드 워셜 의 알고리즘을 사용한다. 플로이드 워셜의 특징으로는 모든간선의 모든정점to 모든정점의 최소 거리를 체크한다. 음의 간선 사용 가능 3중 for문을 돈다 사용해본 결과 foreach 문 을 쓸게 아니라면 아무래도 인접행렬 을 사용하는게 편해보임 but 시간이 좀 걸려보임 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int N, M; static int[][] bus; static int[][] Graph; static int INF ..