개발 정리 모음집

0-1 BFS 가중치가 0, 1로 주어진 그래프에서 최단경로를 찾아낼 수 있는 알고리즘 O(V+E)의 시간 복잡도를 가진다.(V : 정점 개수, E : 간선 개수) 1. 시간복잡도 O(V+E)의 시간복잡도를 가지는 이유는 무엇일까? 1️⃣ Queue 대신 Deque 사용 0-1 BFS는 Deque(덱) 자료구조를 사용해서 구현한다. Deque은 Double Ended Queue로 양 방향에서 offer, poll이 가능하다. 가중치가 0인 간선으로 이동할 경우, 해당 정점을 덱의 앞부분에 추가한다. 이는 그 정점을 가능한 한 빨리 다시 탐색하기 위해서이다. 가중치가 1인 간선으로 이동할 경우, 해당 정점을 덱의 뒷부분에 추가한다. 이는 그 정점을 나중에 탐색하도록 한다. 2️⃣ 한 번씩만 처리되는 정점과..

백준 녹색 옷 입은 애가 젤다지? (골드 IV ) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; // 녹색 옷 입은 애가 젤다지?(골드 4) // 다익스트라 public class Main { static int[][] zelda; static boolean[][] visited; static int N; static int cnt = 0; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReade..

백준 N과 M(3) (실버 Ⅲ) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class N과M_3 { static int n; static int m; static StringBuilder sb = new StringBuilder(); static int[] path; public static void main(String[] args) throws IOException { BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); Stri..

백준 N과 M(2) (실버 Ⅲ) 1. 가지치기 import java.util.Scanner; public class Main { static int n; static int m; static int[] path = new int[9]; static boolean[] used = new boolean[9]; static StringBuilder sb = new StringBuilder(); public static void main(String[] args) { Scanner scanner = new Scanner(System.in); n = scanner.nextInt(); m = scanner.nextInt(); run(0, 0); System.out.println(sb); } private stati..