문제

BOJ 2668: 숫자고르기 https://www.acmicpc.net/problem/2668

풀이

• 윗 줄의 수를 출발지로, 아랫 줄을 도착지로 하여 그래프를 그려본다.

  위 문제에 있는 예시를 이용하면,
  2 -> 1 <-> 3 // 5<->5 <- 4 <- 6 <- 7
  이런식으로 된다.
  여기서 아래 3가지가 사이클이 된다
  1 -> 3 -> 1
  3 -> 1 -> 3
  5 -> 5

• 사이클 발생 여부는 DFS를 사용하여 출발 숫자 -> arr[출발 숫자] -> arr[arr[출발 숫자]] 이런 방법으로 한 방향 탐색을 해준다.
• 탐색 중 출발 숫자를 만나게 되면 하나의 사이클이 되고 list에 넣어준다.

코드

import java.util.*;
import java.io.*;

public class Main {
	
	static int N;
	static int[] arr;
	static boolean[] isVisited;
	static ArrayList<Integer> list;
	
	public static void main(String[] args) throws IOException{
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		arr = new int[N+1];

		for(int i=1; i<=N; i++) {
			arr[i] = sc.nextInt();
		}
		sc.close();
		list = new ArrayList<>(); // 발생한 사이클을 넣을 리스트
		isVisited = new boolean[N+1]; // 방문처리
		
		// 순서대로 사이클이 발생하는지 dfs로 확인
		for(int i=1; i<=N; i++) {
			isVisited[i] = true;
			dfs(i, i);
			isVisited[i] = false;
		}
		
		Collections.sort(list); // 리스트를 오름차순으로 정렬
		System.out.println(list.size());
		for(int i=0; i<list.size(); i++) {
			System.out.println(list.get(i));
		}
		
	}
	
	static void dfs(int start, int target) { // 시작과 다음의 인덱스를 파라미터로 넣어줌
		if(!isVisited[arr[start]]) {
			isVisited[arr[start]] = true;
			dfs(arr[start], target);
			isVisited[arr[start]] = false;
		}
		
		// 사이클이 발생했다면 마지막 수를 넣어줌
		if(arr[start] == target) {
			list.add(target);
		}
	}
	
}

정리

• 그래프 방식을 써야 한다는 것 까지는 생각해 냈는데 dfs 구현을 하는 데 오래 걸렸다.