알고리즘 DFS와 BFS 기본 문제 import java.io.IOException; import java.util.ArrayList; import java.util.Collections; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class DFS와BFS { static int N, M, V; public static void main(String[] args) throws IOException { // BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); Scanner sc = new Scanner(System.i..
알고리즘 완탐 유형. 마름모의 크기를 잘 생각해서 완탐을 돌리면 되는 문제. 마름모를 중점에서 깊이를 생각해서 bfs를 돌려서 만들었음. 그냥 배열로 푸는게 시간, 메모리도 절약할듯. ( 이유 : 불필요한 방문배열과 Queue를 사용해야 함. 조건만 잘 준다면 그냥 배열로도 쉽게 풀 수 있는 문제.) 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 홈방범서비스 { static int T, N, M, map[][]..
미세먼지가 한번에 증식하기 때문에 QUEUE를 사용함. 단 -1인 공기청정기도 존재하기 때문에 PriorityQueue를 사용해서 미세먼지 먼저 처리해 줌. 그 이후 한칸씩 이동하는 부분은 들어오는 순서대로 덮어씀 (나가는 순으로 처리하면 값 저장할 배열 필요) package baekjoon; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.PriorityQueue; import java.util.StringTokenizer; public class 미세먼지안녕_17144 { static int R, C, T, map[][], Ans, arr[]; stati..
다리만들기 2 DFS 와 MST를 이용한 풀이. DFS로 섬의 개수와 위치를 파악하고 크루스칼을 사용하여 풀이 하였음. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Collections; import java.util.StringTokenizer; public class 다리만들기2_17472 { static int N, M, map[][], index = 2, parents[]; static int[] dr = { -1, 1, 0, 0 }; static int[] dc = { 0, 0, -1, 1 }; ..
프림과 크루스칼을 이용한 MST 구하는 문제 프림과 크루스칼의 차이 : 프림은 정점의 리스트를 크루스칼은 간선의 리스트를 저장해야 한다!! ※ 간만프 간적쿠 (공식처럼 외우기) * 프림과 다익스트라 코드가 비슷하니 잘 이해하고 넘어가자 Prim 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; public class 하나로_prim { static int T, N, arr[][];..
다익스트라 알고리즘을 활용한 풀이 * 다익스트라 코드와 프림코드가 상당히 유사함. dis배열의 값을 갱신할 때, 더해서 넣냐 그냥 최소값만 넣냐 차이. (더해서 넣는 경우가 다익스트라) 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; public class 최단경로_1753 { static int V, E, start; static ArrayList[] list; static c..
Kruskal은 간선리스트, Prim은 정점리스트를 사용한다. Kruskal 알고리즘 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.Collection; import java.util.Collections; import java.util.StringTokenizer; public class 최소스패닝트리_1197_kruskal { static int V, E, parents[]; static class Point implements Comparable { int ..
알고리즘 풀이 dfs는 100x100이라 힘들다.. bfs로 풀어야 하는데 최단거리가 아닌 값이 가장 작은 수를 구해야 함. 값을 더해가면서 저장하는데 값이 가장 작은 것부터 계속 더해 나가야 하기 때문에 우선순위 큐를 사용하여 더한 값이 작은 순으로 실행. 결론에 도달했을 때는 가장 작은 값이 저장 됨 -> 정답 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.PriorityQueue; public class 보급로 { static int T, N, map[][], Ans = Integer.MAX_VALUE; static boolean[][] v; stat..