DFS5 [BFS + DFS] 백준 1260번 문제그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. 문제분석DFS와 BFS를 차례대로 구현하면 된다.주의할점은 정점번호가 작은 것을 먼저 방문하므로, 인접 인덱스를 정렬을 해서 방문할 순서를 정해야.. 2024. 11. 18. [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] 백준 2023번 문제수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다.7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수이고, 7도 소수이다. 즉, 왼쪽부터 1자리, 2자리, 3자리, 4자리 수 모두 소수이다! 수빈이는 이런 숫자를 신기한 소수라고 이름 붙였다.수빈이는 N자리의 숫자 중에서 어떤 수들이 신기한 소수인지 궁금해졌다. N이 주어졌을 때, 수빈이를 위해 N자리 신기한 소수를 모두 찾아보자.( 1 문제분석총 4자리라는 가정하에 문제분석 시작1. 첫번째자리수부터 소수인지 체크하면서 4자리까지 소수 체크가 일어나야한다2. 해당 구현을 DFS를 이용하여, 한개씩 체크하며 소수인지 체크한다3. 4자리까지 소수인지 확인.. 2024. 11. 16. [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 다음
