알고리즘/백준
[백준 2668] 숫자고르기 (C++)
라이언납시오
2020. 4. 9. 10:06
728x90
반응형
문제 링크: https://www.acmicpc.net/problem/2668
2668번: 숫자고르기
세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절히 뽑으면, 그 뽑힌 정수들이 이루는 집합과, 뽑힌 정수들의 바로 밑의 둘째 줄에 들어있는 정수들이 이루는 집합이 일치한다. 이러한 조건을 만족시키도록 정수들을 뽑되, 최대로 많이 뽑는 방법을 찾는 프로그램을 작성하시오. 예를 들어, N=7인 경우 아래
www.acmicpc.net
1. 주의할 점
- 그래프로 생각 -> DFS로 접근 -> 중복된 숫자 처리
2. 구현
- 그래프로 생각하여 Arr[]배열에 1~Num까지 가리키는 Node의 번호를 입력 받는다
- 각 Node마다 시작하여 첫 시작점을 기준으로 순환하는 형태가 이루어진다면 Ans 벡터에 담는다(단, 이미 1번 이상 담은 Node는 넣지 않는다)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int arr[101], num, start;
bool visit[101];
bool check[101] = { false, };
vector<int> ans;
void dfs(int idx) {
//되돌아 오는 경우
if (idx == start && visit[idx]) {
for (int i = 1; i <= num; i++)
if (visit[i] && !check[i]) {
ans.push_back(i);
check[i] = true;
}
return;
}
if (visit[idx]) return;
visit[idx] = true;
int next = arr[idx];
dfs(next);
}
int main() {
cin >> num;
for (int i = 1; i <= num; i++)
cin >> arr[i];
for (int i = 1; i <= num; i++) {
for (int j = 1; j <= num; j++)
visit[j] = false;
start = i;
dfs(i);
}
sort(ans.begin(), ans.end());
cout << ans.size() << '\n';
for (int i = 0; i < ans.size(); i++)
cout << ans[i] << "\n";
system("pause");
return 0;
}728x90
반응형