목록백준/bfs, dfs (47)
Study hard
https://www.acmicpc.net/problem/2331 2331번: 반복수열 첫째 줄에 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 출력한다. www.acmicpc.net [풀이] dfs를 사용하여 풀었다. 수열을 구하면서 check[값]을 해당 값이 나올 때마다 +1해주다가 어떤 값이 3번 나오면 반복수열이 되었다는 뜻이므로 함수에서 빠져나온다. ex) 37, 58, 89, 145, 42, 20, 4, 16, 37, 58, 89, 145, 42, 20, 4, 16, 37, ... 이렇게 37이 세번 나와야 반복수열이 되었다는 것을 알 수 있다. check값이 1인 인덱스들이 반복되는 부분을 제외했을 때 수열에 남게되는 수들이다. #include #include //pow u..
https://www.acmicpc.net/problem/10451 10451번: 순열 사이클 문제 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 www.acmicpc.net [풀이] bfs를 이용하여 풀었다. 이어진 정점을 방문하다가 처음 시작했던 정점이 나오면 순열 사이클이므로 개수를 갱신해 주었다. #include #include #include //memset using namespace std; int T, N; int P[1001];//순열 저장 bool check[1001];//방문한 정..
https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net [풀이] bfs와 dfs로 모든 정점을 돌면서 서로 이어진 정점들을 다른 그룹에 넣는 방식으로 풀었다. #include #include #include using namespace std; int K, V, E; vectorGraph[20001];//각 정점에 연결된 간선 저장 int Group[20001];//그룹 1, 그룹 2, 0이면 아직 방문X void init() { for ..
https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주�� www.acmicpc.net [풀이] 연결 요소 : 한 개 이상의 간선으로 연결된 정점들로 이루어진 그래프.(서로 아무 관련 없는 각각의 그래프) 연결 요소 조건 - 연결 요소에 속한 모든 정점을 잇는 경로가 존재해야 함. - 다른 연결 요소에 속하는 정점과 이어지는 경로가 있으면 안됨. 방문을 체크하는 배열을 만들어서 체크하지 않은 정점을 시작점으로 bfs를..
https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net dfs알고리즘, bfs알고리즘 #include #include #include //memset using namespace std; int N, M, V; int Graph[1001][1001];//이어진 정점들 1 표시 bool check[1001]; void dfs(int curV) { check[curV] = true; cout V; for (int i ..