전공공부

설명 정말 간단한 다익스트라 구현 문제 같지만 그렇지만은 않은 것이 해당 부분이 문제 였었습니다. 저는 아래 부분을 풀때, 처음에는 우선 넘긴다음 다음 차례로 들어온 것에 대해서 visited와 함께 걸러내는 식으로 만들었는데요. private static void dijkstra(int start) { boolean visited[] = new boolean[N + 1]; Queue q = new PriorityQueue(); q.add(new Data(start,0)); int[] weight = new int[N + 1]; while (!q.isEmpty()){ Data now = q.poll(); if(visited[now.to] || weight[now.to] > M){ continue; } v..

설명 가중치가 부여된 그래프 상에서 단방향 일 때 모든 정점 쌍 간의 최단 경로를 찾는 알고리즘인 플로이드 와샬 알고리즘을 사용하면 거리를 쉽게 구할 수 있습니다. 먼저 2차원 배열을 초기화 합니다. 각 배열의 정점에서 다른 모든 정점으로의 직접적으로 도착하는 이동거리를 찾습니다. 그 후, 알고리즘 상세를 살펴 보자면 X -> Y 까지의 최소 비용을 구한 것arr[X][Y]으로 이러한 방식으로 비용을 찾아나가는데. 예시로 X -> Y -> Z 가 만일, X->Z 최소 이동거리라면 arr[X][Y] + arr[Y][Z]를 구합니다. 즉, for문을 보면 알겠지만 출발지 i , 목적지 j, 중간 지점을 k로 둡니다. 이미 i -> j가 최소인 경우에는 탐색을 하지 않겠지만 만일, k를 거쳐서 갈 때 최소가 ..

설명 다익스트라를 사용해서 직접 각 시작점에서 시작해서 가지는 모든 곳을 체크했습니다. 또한, 처음 시작하는 곳은 내가 이미 시작 할 때 방문 한 여부를 찾는것이 아닌 다른 지점에서 처음 시작 지점을 들어오는 것을 체크하는 것이라서 그에 대한 방문 처리를 해주었습니다. 코드 package shortest_path; 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 BOJ_11403 { static int[][] m..

설명 다익스트라 알고리즘을 사용했다고 생각했으나 사실 가물가물하여 이것이 다익스트라의 형태가 맞는 것인지 헷갈린다. 그저 방문 체크 여부를 하고 이전 거리로 부터 가져온 거리 웨이트 값을 더해서 이런 형태로 풀었다. 코드 package shortest_path; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; public class BOJ_18352 { static List[] graph; public static void main(String[] args) throws Exception{ BufferedReader in = new BufferedReader(new InputStreamReader(Sy..

설명 PRIM으로 풀고 성별에 따른 의존성을 Data 객체에 추가했다. 그리고, 이를 모두 다 이어지지 못한 경우에 예외처리를 더하여 문제의 조건을 알맞게 맞췄다. 코드 package MST; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; import java.util.PriorityQueue; import java.util.StringTokenizer; public class BOJ_14621 { private static class Data implements Comparable{ int en..

설명 타입만 잘 지정하면 된다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.PriorityQueue; import java.util.StringTokenizer; public class Main { static class Data implements Comparable{ int end; int weight; public Data(int end, int weight) { this.end = end; this.weight = weight; } @Override public int compareTo(Da..

설명 자료형 때문에 꽤나 애 먹었던 문제다. long 캐스팅이 잘 안 되어서 오래걸렸다. Prim 알고리즘을 사용했고 입력으로 들어오는 값은 거리를 구하는 것에 사용하고 list의 인덱스는 거리가 입력으로 들어오는 순서에 따라서 지정을 하고 이에 따른 거리값을 weight 값으로 넣었다. 코드 package MST; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; import java.util.PriorityQueue; import java.util.StringTokenizer; public class BOJ_1774 { static class D..

설명 프림 알고리즘을 활용하여 인접 행렬을 인접 리스트 형식으로 받아서 처리했다. 코드 package MST; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.PriorityQueue; import java.util.StringTokenizer; public class BOJ_16398 { static class Data implements Comparable { int end; int weight; public Data(int end, int weight) { this.end = end; this.weigh..