[백준 - 2668] 골드5 숫자고르기

www.acmicpc.net/problem/2668

2668번: 숫자고르기

 

1. 유형

dfs

 

2. 풀이

싸이클 발생 여부를 판단한다.

처음 입력값을 보고 그래프를 생각 해야한다

 

3. 코드

처음 풀이 ->  조합 이용, N이 100개나 되기 때문에 잘못된 방법이다.

import java.util.Scanner;

public class Test {
	static int N, map[][], answer=0,ans[];
	static boolean visit[][];
	static int list[];
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N=sc.nextInt();
		map = new int[2][N+1];
		visit = new boolean[2][N+1];
		list = new int[N];
		ans = new int[N];
		for (int i = 1; i <= N; i++) {
			map[0][i] = i;
			map[1][i] = sc.nextInt();
		}
		go(1, 0);
		System.out.println(answer);
		for (int i = 0; i < answer; i++) {
			System.out.println(ans[i]);
		}
	}
	static void go(int idx, int size) {
		if(idx==N) {
			int temp=0;
			for (int i = 1; i <= N; i++) {
				if(visit[0][i]!=visit[1][i])
					return;
				else if(visit[0][i] && visit[1][i]) {
					list[temp++] = map[0][i];
				}
			}
			if(answer < size) {
				answer =size;
				for (int i = 0; i < answer; i++) {
					ans[i] = list[i];
				}
			}	
			return;
		}
		visit[0][idx] = true;
		visit[1][map[1][idx]]= true;
		go(idx+1, size+1);
		visit[0][idx] = false;
		visit[1][map[1][idx]]= false;
		go(idx+1, size);
	}
}
//2^100이니깐 조합은 아니다
//비트마스킹도 아니다
//

 

dfs풀이

import java.util.Scanner;

public class back_2668숫자고르기 {
	static int map[], current, visit[], cnt=0;
	static boolean cycle[];
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		map = new int[n+1];
		for (int i = 1; i <= n; i++) {
			map[i] = sc.nextInt();
		}
		cycle = new boolean[n+1];
		for (int i = 1; i <= n; i++) {
			visit = new int[n+1];
			visit[i] = 1;
			current = i;
			dfs(i);
		}
		System.out.println(cnt);
		for (int i = 1; i <= n; i++) {
			if(cycle[i])
				System.out.println(i);
		}
	}
	
	static void dfs(int cur) {
		int next = map[cur];
		visit[next]++;
		if(visit[next]==2 && current==next) {
			cycle[current] = true;
			cnt++;
			return;
		}
		if(visit[next]==2) return;
		dfs(next);
	}
}

 

다음 방문 지점이 처음값과 같고 두번 방문했다면 싸이클이 발생한 것

if(visit[next]==2 && current==next)