Study hard

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. � www.acmicpc.net [풀이] bfs탐색을 사용하여 풀었다. 그림처럼 단지마다 1,2,3 표시할 필요는 없고, 각 좌표의 상하좌우를 탐색해 이어져 있는 1의 개수를 구하면 된다. #include #include #include //sort #include //scanf using namespace std; struct Pos { int x, y;//Map의 x좌표, y좌표 }; int N; int Map[26][26]..

https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 문제 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 www.acmicpc.net [풀이] dfs를 이용하여 풀었다. 다음 학생이 처음 방문하는 학생이면 check[학생번호]를 true로 바꾸어주고, 이미 한 번 방문했던 학생을 다시 방문하게 된다면 Recheck[학생번호]가 false일 경우 거쳐왔던 학생만큼 cnt에 저장한다. (cnt는 프로젝트 팀에 속한 학생들의 수이다) ※dfs마지막에 Recheck[현재 학생번호]를 true로 바꿔줘야 같은 싸이클을 그 싸이클에 속하는 원소..

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를..