BFS
🔺 문제 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 ..
🔺 문제 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 8..
🔺 문제 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 🔺 코드 import java.util.*; import java.io.*; public class Main { // 상하좌우 탐색 위한 배열 선언 static int[] dx = {0, 1, 0, -1}; static int[] dy = {1, 0, -1, 0}; static boolean[][] visited; static int[][] A; static int N, M; public static void main(String[] args) throws IOException { B..
목차 🔔 깊이 우선 탐색 (DFS) • 재귀 함수, 스택 → LIFO • 시간 복잡도 : O(V+E) 핵심 이론 - 인접 리스트 & 방문 배열 - 재귀 + 백트래킹 문제 유형 - 단절점 찾기 - 단절선 찾기 - 사이클 찾기 - 위상 정렬 - 연결 요소 개수 / 재귀 깊이 (= DFS 수행 횟수) - 순열 / 조합 DFS 구현 메소드 - 재귀 함수 사용 public static void DFS(int node) { // 1) 종료 조건 : 현재 노드가 이미 방문한 노드인 경우 if(visited[node]) return; // 현재 연결 노드 中 방문하지 않은 노드인 경우 visited[node] = true; // 2) 재귀 for(int i : A[i]) { if(!visited[i]) { DFS(i)..
🔺 문제 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 🔺 코드 import java.util.*; import java.io.*; public class Main { static ArrayList[] A; // 인접 리스트 static boolean[] visited; // 방문 배열 public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new I..
스택 ○ 활용분야 : 깊이 우선 탐색 (DFS), 백트래킹 (재귀) ○ 후입선출 (LIFO) ○ 연산 ▹ top : 삽입/삭제 발생 위치 • push : 데이터 삽입 • pop : 데이터 삭제 • peek : 데이터 단순 확인 • size : 스택에 들어있는 개수 출력 • empty : 스택이 비어있으면 1, 아니면 0 출력 큐 ○ 활용분야 : 너비 우선 탐색 (BFS) ○ 선입선출 (FIFO) ○ 연산 • front : 큐의 가장 앞 데이터 • rear : 큐의 가장 끝 데이터 • add : 데이터 삽입 (rear) • poll : 데이터 삭제 & 확인 (front 부분) • peek : 맨 앞 위치(=front)의 데이터 단순 확인 : (참고) 스택에서 empty() 메소드랑 isEmpty() 메소드..
