깊이우선탐색3 [DFS] 백준 13023번 문제BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다.오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다.A는 B와 친구다.B는 C와 친구다.C는 D와 친구다.D는 E와 친구다.위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오.[조건]첫째 줄에 사람의 수 N (5 ≤ N ≤ 2000)과 친구 관계의 수 M (1 ≤ M ≤ 2000)이 주어진다.둘째 줄부터 M개의 줄에는 정수 a와 b가 주어지며, a와 b가 친구라는 뜻이다. (0 ≤ a, b ≤ N-1, a ≠ b) 같은 친구 관계가 두 번 이상 주어지는 경우는 없다.[출력]문제의 조건에 맞는 A, B, C, D,.. 2024. 11. 17. [DFS] 백준 11724번 문제방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다. 문제분석연결요소란, edge끼리 이어져있는 요소의 개수를 세라는 의미로서, DFS가 한번 끝난 횟수를 의미 (DFS 한번 끝난 경우 : 스택이 비어서 다음 edge값이 들어가기 전까지 )DFS가 한번 끝날때까지의 count를 기록 예제 입력예제 출력6 51 22 55 13 44 62 DFS 핵심이론방문을 기록하여, 재방문없이 모든.. 2024. 11. 15. [탐색] 깊이우선탐색 깊이 우선 탐색이란?그래프 완전 탐색 기법 중 하나이며,그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 진행하는 알고리즘기능특징시간복잡도그래프완전탐색- 재귀함수로 구현- 스택 자료구조 이용O(노드 개수 + Edge 개수) 깊이우선 탐색 주의할점재귀함수를 이용하므로, 스택 오버플로우에 주의해아한다주로 사용되는 문제 유형 : 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상정렬 깊이우선 탐색 핵심 이론한 번 방문한 노드를 다시 방문하면 안됨후입선출(LIFO) 구조를 가진다 (스택 사용)이론을 이용하기 위해서, 스택으로 구현한 것이며 주로 재귀함수를 이용하여 사용한다방문할 스택 + 방문한 곳 저장할 배열탐색 순서 : 1 -> 3 -.. 2024. 11. 15. 이전 1 다음
