알고리즘 섬과 섬을 연결할 수 있는 다리의 길이가 최소인값을 찾는 알고리즘 1. dfs탐색을 통해 섬의 정보를 알아야 함. 각각 넘버링 예) 섬이 3개라면 -> 1번섬, 2번섬, 3번섬 2. 섬의 가장자리 즉, 바다와(0) 근접해있는 곳은 bfs탐색을 시작함 - 탐색 기준은 자신의 넘버와 같지않은곳을 따라가면서 탐색(count + 1) - 해당지점의 넘버링값을 보고 자신의 넘버링값과 다르다면 최소값을 갱신하고 리턴. 단, 현재의 cnt값에서 -1해줘야 함. - 모든섬이 연결되어 bfs를 돌릴 수 없는 경우도 있을 수 있기 때문에 Ans가 Max값이라면 0 출력! 아니면 Ans값 출력 * bfs를 사용한 이유 : 최소값을 찾는 알고리즘이기 때문 import java.io.BufferedReader; imp..
알고리즘 (0,0)에서 (N,M)의 위치까지의 최소 거리를 구하는 알고리즘 dfs, bfs둘 다 풀 수 있지만 최소 거리를 묻는 문제이기 때문에 bfs가 적당하다고 생각함. bfs 풀이 package baekjoon; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class 미로탐색 { static int N, M, map[][]; static int[] dr = { 1, -1, 0, 0 }; static int[] dc = { 0, 0, 1, -1 }; static int Ans = 1; public static void main(String[] args) { Scanner sc = new Sca..
알고리즘 경우의 수가 2가지 * 배달시간을 (공격 + 대기)로 나눈 나머지가 0이 아닐 때 * 나온값에 공격시간을 뺀값이 0이하면 물림 문제를 잘 파악하고 경우의 수만 찾아낼 수 있다면 쉽게 풀 수 있는 문제 package baekjoon; import java.util.Scanner; public class 사나운개 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int A, B, C, D; int P, M, N; int result = 0; int result1 = 0; int result2 = 0; A = sc.nextInt(); B = sc.nextInt(); C = sc.nextInt(); D = sc..
알고리즘 조건이 있는 완전탐색 문제. 물의 높이를 1씩 증가시키면서 탐색을 돌면 풀 수 있음. bfs탐색 package baekjoon; 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 안전영역bfs { static int N, map[][]; static int[] dr = { -1, 1, 0, 0 }; static int[] dc = { 0, 0, -1, 1 }; static boolean[][] v; sta..
알고리즘 ※불과 사람의 배열을 따로 쓰기위해 체크배열을 각각 사용함. 불 부터 bfs를 돌리고 그다음 사람을 기준으로 bfs를 돌림. 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 불_5427 { static int T, w, h, Ans; static char[][] map; static int[] dr = { -1, 1, 0, 0 }; static int[] dc = { 0, 0, -1, 1 }; stati..
알고리즘 연결리스트를 만든 후 부분집합을 사용하여 구를 나누고 bfs를 돌려 연결되어 있는지 확인 연결되어 있다면 인구수의 최소값을 구함. package baekjoon; import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class 게리맨더링_17471 { static int arr[], N, Ans = Integer.MAX_VALUE; static boolean[] v; static ArrayList[] list; public static void main(String[] args) { Scanner sc = new Scanner(System.in);..
알고리즘 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..