2668 숫자고르기

BOJ::2668 숫자고르기

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

dfs를 통해 cycle을 찾아주면 된다.

sx = 시작점으로 놓고 

이미 방문한 지점을 한번 더 방문한경우 

- 그 지점이 시작점(sx)이면 cycle        

-  시작점이 아니면 cycle이 아님.

으로 풀었다.

<Cpp>

#include <iostream>
#include <vector>
#include <algorithm>
#include <memory.h>
using namespace std;
 
int group[101];
bool check[101];
int n, x;
vector<int> res;
 
void dfs(int x, int sx) {
    //시작한 숫자로 돌아 왔으면 종료
    if (x == sx) {
        for (int i = 1; i <= n; i++) {
            if (check[i]) {
                res.push_back(i);
                group[i] = 0;
            }
        }
        return;
    }
    
    //이미 사이클 확인 끝난 경우
    if (check[x] || group[x] == 0) return;
 
    check[x] = true;
    dfs(group[x], sx);
}
 
int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n;
    
    for (int i = 1; i <= n; i++) {
        cin >> x;
        group[i] = x;
    }
    
    for (int i = 1; i <= n; i++) {
        //이미 체크 끝난 경우
        if (group[i] == 0)continue;
 
        //위와 아래 숫자 같은 경우
        if (group[i] == i) {
            res.push_back(i);
            continue;
        }
 
        memset(check, 0, sizeof(check));
        check[i] = true;
        dfs(group[i], i);
    }
 
    sort(res.begin(), res.end());
    cout << res.size() << "\n";
    for (auto &a : res) {
        cout << a << "\n";
    }
}

<JAVA>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
 
public class Main {
    
    static int n,sx;
    static int a[]=new int[101];
    static boolean visited[];
    
    public static void main(String args[]) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n=Integer.parseInt(br.readLine());
        for(int i = 1 ; i <= n ; i++){
            a[i]=Integer.parseInt(br.readLine());
        }
        
        ArrayList<Integer> res = new ArrayList();
        for(int i = 1 ; i <= n ; i++){
            visited=new boolean[n+1];
            sx = i;
            if(dfs(i)){
                res.add(i);
            }
        }
        
        Collections.sort(res);
        System.out.println(res.size());
        for(int vv : res){
            System.out.println(vv);
        }
 
    }
    
    public static boolean dfs(int v){
        if(visited[v]){
            if(v==sx){
                return true;
            }
            return false;
        }
        else{
            visited[v]=true;
            if(dfs(a[v])){
                return true;
            }
            return false;
        }
        
    }
}