[DFS]백준2668번 숫자고르기

백준2668

처음에는 문제를 제대로 읽지 않아,

i == arr[arr[i]]

인 경우를 얘기하는 줄 알았다.

그게 아니라, 첫 째줄에서 몇 개의 숫자를 뽑았을 때 둘 째 줄의 숫자들의 집합도 같은지를 확인하는 거였다.

이 경우는 주어진 배열로 그래프를 만들었을 때 사이클이 생기는지 확인하는 것과 같은 경우다.

문제에서 주어진 경우를 보면,

1→3→3→1 의 경우가 있는데, 이것은 1에서 시작해 1로 온 것이다.

사이클에 포함되는 요소들만 배열에 추가하면 결국은 짝이 맞기 때문에 우리가 원하는 결과를 얻을 수 있다.

DFS를 이용해 사이클인지 확인하며 사이클이라면 포함된 요소를 한 번에 찾아도 되지만, N 의 범위가 1부터 100까지기 때문에 각각의 노드에 대해서 사이클이 생기는지 확인해 사이클이 생긴다면 추가해주면 된다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

int arr[101];
bool answered[101] = {false,};
bool visited[101] = {false,};
vector<int> answer;
void dfs(int start, int current){
    if(current==start && visited[current]){
        answer.push_back(start);
    }
    if(!visited[current]){
        visited[current] = true;
        dfs(start,arr[current]);
    }

}
int main(){
    int N;

    cin >> N;
    for(int i=1;i<=N;i++){
        cin >> arr[i];
    }

    for(int i=1;i<=N;i++){
        memset(visited,false,sizeof(visited)); 
        dfs(i,i);
    }
    
    cout << answer.size() << endl;
    sort(answer.begin(),answer.end());
    for(int i=0;i<answer.size();i++){
        cout << answer[i] << endl;
    }
}

BFS를 이용한 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

int arr[101];
bool answered[101] = {false,};
vector<int> answer;
int main(){
    int N;

    cin >> N;
    for(int i=1;i<=N;i++){
        cin >> arr[i];
    }
    for(int i=1;i<=N;i++){
        if(!answered[i]){
            bool visited[101] = {false,};
            vector<int> tmp;
            tmp.push_back(i);
            queue<int> q;
            q.push(i);
            visited[i]=true;
            // cout << endl;
            while(!q.empty()){
                int cur = q.front();
                q.pop();
                if(arr[cur] == i){
                    for(int j = 0;j<tmp.size();j++){
                        answer.push_back(tmp[j]);
                        answered[tmp[j]] = true;
                    }
                }
              
                if(!visited[arr[cur]]){
                    q.push(arr[cur]);
                    tmp.push_back(arr[cur]);
                     visited[cur] = true;
                    //  int temp;
                    // cin >> temp;
                    // cout << "i is " << i << ", " <<cur <<" and " << arr[cur] << endl;
                }
            }
        }
        // cout << endl;
    }
    cout << answer.size() << endl;
    sort(answer.begin(),answer.end());
    for(int i=0;i<answer.size();i++){
        cout << answer[i] << endl;
    }
}