huhsae's day huhsae's day

2188 축사 2188 축사https://www.acmicpc.net/problem/2188 분류네트워크 유량애드몬드-카프 알고리즘BFS이분 매칭 TIPS포드 - 풀거슨 알고리즘을 풀 때, v -> u로 가는 용량이 주어진다면, u -> v로 가는 용량 0의 간선을 만들어 주어야 한다.코드에서는 capacity[][] 배열을 사용해서 그래프를 나타내준다면, 초기값이 0이기 때문에 1번의 내용을 생각해줄 필요가 없다. 하지만 간선 찾는 시간을 단축시키기 위해 인접리스트로 그래프를 표현했다면, 꼭 인접리스트에 반대로 가는 가상의 간선을 만들어주어야한다. 처음부터 그래프를 배열로 했다면 상관없다.이분 매칭은 source와 sink가 여러개인 네트워크 유량문제에서 super source와 super sink를 ..

1504 특정한 최단 경로백준 특정한 최단 경로 Tip다익스트라 알고리즘 활용다익스트라 알고리즘은 출발점에서 모든 정점에 대한 최단거리를 구하는 알고리즘이다.꼭 들려야 하는 정점을 끝나는 지점으로 하는 다익스트라를 여러번 돌려 원하는 값을 찾을 수 있다. CODE​ximport java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;​public class BOJ_1504 {​ static final int INF = 800000; static List[] map; static int node; static int edge;​ public static void main(Strin..

11657 타임머신 11657 타임머신https://www.acmicpc.net/problem/11657 Algorithm최단거리벨만 - 포드 알고리즘 CODEimport java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Arrays;import java.util.StringTokenizer;​public class BOJ_11657 { static int N; static int M; static int[] dist; static int[][] map; static ArrayList[] list;​ static BufferedR..

1735 최단경로백준 1735 최단경로 알고리즘최단경로 ( 다익스트라) -개념정리 CODEimport java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;​public class BOJ_1753 {​ public static void main(String args[]) throws IOException { ArrayList[] graph; Queue pq = new PriorityQueue();​ //init​ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st ..

1238 파티https://www.acmicpc.net/problem/1238 TIPS최단경로 문제플로이드 다익스트라 알고리즘을 해결할 수 있다.플로이드로 풀경우 O(|V|^3^) 속도 때문에 안풀리 수 있다고 하는데, 조건과 관계없이 풀수 있다.플로이드로 풀경우 단순히 학생집에서 파티장의 최단거리, 파티장에서 학생집까지의 최단거리를 더해서 값을 구할 수 있다.다익스트라로 풀경우, 파티장에서 학생집까지는 쉽게 구할수 있다. 하지막 역은 모든 정점을 다시 구해야 하는 불편함이 있다. 이를 해결하기 위해서, 간선의 방향을 바꿔서 파티장에서 각 노드까지의 간선의 합을 구하면 쉽게 구할 수 있다고 한다. CODEimport java.io.BufferedReader;import java.io.IOException..

https://www.acmicpc.net/problem/1826 https://github.com/huhsay/algorithm/blob/master/heap/src/BOJ_1826.java TIPS 우선순위큐(힙) ALGORITHM 두개의 우선순위 큐를 사용합니다.먼저 입력값을 받으며, 거리를 기준으로 가까운 주유소를 정렬합니다. (stations) while문으로 내가 갈 수 있는 거리가 목표지점에 미치지 못한다면 목표지점을 찾을 때까지 반복하도록 합니다.while문 안에서 현재 내가 도달할수 있는 범위에 있는 주유소가 있다면stations 배열에서 객체를 꺼내어 새로운 우선순위 큐에 넣습니다.(reachableStations)reachableStation은 연료가 많은 순으로 정렬됩니다. 만약 r..