[BaekJoon] 2668 숫자고르기

1.  문제 링크

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

2.  문제

요약

• 세로 두 줄, 가로 N개의 칸인 표가 주어집니다.
• 첫 번째 줄의 각 칸에는 정수 1, 2, 3, ..., N이 순서대로 들어 있고 두 번째 줄의 각 칸에는 1보다 크거나 같고 N보다 작거나 같은 정수가 들어 있습니다.
• 첫 번째 줄에서 숫자를 적절히 뽑으면 뽑힌 정수들이 이루는 집합과 뽑힌 정수들의 두 번째 줄에 들어있는 정수들이 이루는 집합이 일치하는 조건을 만족시키도록 정수들을 뽑습니다.
• 위 조건을 만족시키면서 최대로 많이 뽑으려고 할 때, 뽑힌 정수들을 찾아내는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 100보다 작거나 같은 N이 주어지고 두 번째 줄부터 N개의 줄에는 정수들이 차례대로 주어집니다.
• 출력: 첫 번째 줄에 뽑힌 정수들의 개수를 출력하고 두 번째 줄부터 뽑힌 정수들을 오름차순으로 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;

public class Main {
	static Integer[] nums;
	boolean[] visited;
	static ArrayList<Integer> visit_num;
	public void findEqualSet(int start, int target) {
		if(!visited[nums[start]]) {
			visited[nums[start]] = true;
			findEqualSet(nums[start], target);
			visited[nums[start]] = false;
		}
		if(nums[start] == target) {
			visit_num.add(target);
		}
	}
	
	public void getEqualSet() {
		visit_num = new ArrayList<Integer>();
		visited = new boolean[nums.length];
		for(int i = 1; i < nums.length; i++) {
			visited[i] = true;
			findEqualSet(i, i);
			visited[i] = false;
		}
		Collections.sort(visit_num);
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int num = Integer.parseInt(br.readLine());
		nums = new Integer[num + 1];
		for(int i = 1; i <= num; i++) {
			nums[i] = Integer.parseInt(br.readLine());
		}
		br.close();
		Main m = new Main();
		m.getEqualSet();
		bw.write(visit_num.size() + "\n");
		for(int i = 0; i < visit_num.size(); i++) {
			bw.write(visit_num.get(i) + "\n");
		}
		bw.flush();
		bw.close();
	}
}

4.  접근

• 해당 문제는 DFS를 이용하여 해결할 수 있습니다.
• 뽑힌 정수의 집합 및 뽑힌 정수들의 두 번째 줄에 있는 정수들의 집합이 일치하는 정수 집합을 뽑아야 하는데 이러한 집합은 싸이클을 이룹니다.
• 즉, 위 예를 참고하면
  • 1 -> 3 -> 1
  • 3 -> 1 -> 3
  • 5 -> 5
• 이렇게 숫자들이 싸이클을 이루게 됩니다.
• 즉, 주어진 숫자들에서 싸이클이 발생하는 숫자 집합을 뽑아내는 문제입니다.
• 싸이클 발생 여부는 DFS를 통해 확인합니다.
• 싸이클이 발생하는지 탐색할 숫자와 싸이클을 이루어 본인에게 돌아와야하므로 탐색하려는 숫자를 의미하는 타겟 숫자 두 숫자를 이용하여 탐색하려는 숫자의 두 번째 줄에 있는 숫자가 타겟 숫자가 될 때까지 DFS를 통해 탐색을 진행하고 본인에게로 돌아오는 싸이클이 발생한다면 해당 숫자를 집합에 넣어줌으로써 문제에서 요구하는 집합을 찾습니다.

public void findEqualSet(int start, int target) {
	if(!visited[nums[start]]) {
		visited[nums[start]] = true;
		findEqualSet(nums[start], target);
		visited[nums[start]] = false;
	}
	if(nums[start] == target) {
		visit_num.add(target);
	}
}

1. 주어진 수를 1차원 배열 nums에 index 1부터 차례대로 설정하고 싸이클을 이루는 숫자를 넣을 ArrayList visit_num을 생성하며 DFS를 진행할 때, 해당 숫자를 방문하였는지를 나타내는 1차원 배열 visited를 생성합니다.
2. 주어진 모든 숫자들을 확인하면서 문제에서 원하는 정수 집합을 구합니다.
   1. 탐색하려는 숫자는 방문하였으므로 해당 위치의 visited 값을 true로 변경합니다.
   2. 탐색하려는 숫자가 싸이클을 이루고 있는지 확인하고 해당 숫자가 싸이클을 이루고 있다면 visit_num에 해당 숫자를 추가합니다.
      1. 만약 탐색하려는 숫자의 두 번째 줄에 있는 숫자를 아직 방문하지 않았다면 해당 숫자를 방문하므로 해당 숫자 위치에 해당하는 visited 값을 true로 변경합니다.
      2. 탐색하려는 숫자의 두 번째 줄에 있는 숫자와 target 숫자를 이용하여 재귀함수를 호출하고 탐색하려는 숫자의 두 번째 줄에 있는 숫자와 target 숫자가 같다면 싸이클을 이루는 것이므로 target 숫자를 visit_num에 추가합니다.
      3. 탐색하려는 숫자에 대해 탐색을 마쳤다면 다음 탐색을 위해 해당 위치의 visited 값을 false로 변경합니다.
3. 2번의 반복문이 끝난 후에 visit_num을 오름차순으로 정렬하고 visit_num의 길이와 오름차순으로 정렬한 싸이클을 이루는 수들을 출력합니다.