[BAEKJOON] 2668번 숫자고르기

https://www.acmicpc.net/problem/2668

2668번: 숫자고르기

문제조건

1.  첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있다.
2.  둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다.
3.  첫째 줄에서 숫자를 적절히 뽑으면, 그 뽑힌 정수들이 이루는 집합과, 뽑힌 정수들의 바로 밑의 둘째 줄에 들어있는 정수들이 이루는 집합이 일치한다.
4. 숫자를 최대로 뽑는 경우, 뽑는 숫자들을 출력하라.

접근방법

 

모든 경우의 수를 따져서 비교해줄려고 DFS를 생각했지만 시간복잡도가 너무 컸다.

계속해서 방법을 떠올려 보는데 도무지 잘 생각이 나질 않았다.

단순하게 생각해보니, 어차피 첫째 줄 배열은 1부터 N까지 항상 고정이고, 중복된 것이 없으므로 for문 돌면서 하나씩 이게 둘째 줄의 배열에 포함되는 것인지 확인 해주면 되는 것이었다.

다만 뽑힌  정수 밑에 해당하는 집합을 알아야 하기 때문에 단순하게 for문만 돌려서는 안된다.

ex)  위 예시대로 배열이 있고, 첫째 줄에서 1을 탐색했다고 하자.
1을 고르는 것이 맞는지 어떻게 알 수있을까? 둘째 줄의 3을 첫째줄에서도 가지고 있어야하고, 또 다시 첫째 줄의 3은 둘째 줄의 1을 가지고 있어야한다.
반면 첫째 줄의 2를 한번 보자. 2의경우에는 둘째 줄이 1이므로, 첫째줄의 1이 둘째 줄의 2를 가지지않고, 3을 가지므로 집합에 포함되지 않는다.

 

위에 장황하게 예시를 풀어 놨는데, 정리해보면 그래프적 관점으로 접근해서 사이클이 있으면 첫째줄에서 뽑는 숫자로 선택한다는 말이다!

 

소스코드

#include <iostream>
#include <vector>
#include <string.h>
using namespace std;

int n, arr[101], visited[101];
vector<int> res;
void dfs(int idx, int s){
	if(visited[idx]){
		if(s == idx) res.push_back(idx);
		return;
	}
	visited[idx] = 1;
	dfs(arr[idx], s);
}

int main(){
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> arr[i];
	for(int i = 1; i <= n; i++){
		memset(visited,0,sizeof(visited));
		dfs(i,i);
	}
	cout << res.size() << '\n';
	for(int i = 0; i < res.size(); i++) cout << res[i] << '\n';
	return 0;

}

 

요새 구현문제를 많이 풀었더니, 간단한 코드여도 알고리즘적으로 생각하는게 좀 어려운 것 같다. 연습많이하자,,,!