[BOJ] 숫자고르기-2668

---

코드

package dfs.Day250304;

import javax.swing.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Day01_숫자고르기_re {
    static boolean[] checked;
    static int[] arr;
    static List<Integer> result = new ArrayList<>();
    static int num;

    public static void dfs(int i) {
        if (arr[i] == num) {
            result.add(i);
        }

        if (!checked[arr[i]]) {
            checked[arr[i]] = true;
            dfs(arr[i]);
            checked[arr[i]] = false;
        }

    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        arr = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine()) - 1;
        }
        checked = new boolean[n];

        for (int i = 0; i < n; i++) {
            checked[i] = true;
            num = i;
            dfs(i);
            checked[i] = false;
        }

        System.out.println(result.size());
        Collections.sort(result);
        for (int i : result) {
            System.out.println(i + 1);
        }
    }
}

---

문제

오늘은 숫자고르기 라는 문제를 풀었습니다.
우선 처음 20분동안은 문제 자체를 이해하지 못해서 gpt한테 도움을 받았습니다..

1첫번째 테이블에 0번째 인덱스를 보시면 { 1, 3 } 이 있습니다.
2번째 테이블을 보면 2 인덱스에는 {3 , 1 }이 있습니다. 그러면 정답으로 처리합니다.

처음에 테이블1, 테이블2에 공통된 숫자를 찾으라는걸로 알아들음

대참사

블로그 10개 정도 찾아가면서 봐도 이해가 되지 않았습니다. 처음에는 뭔 소리인가 싶었습니다.
오후 10시쯤에 집에 도착하고도 계속 보다가 그냥 반포기 상태로 침대에 누워서 유튜브 영상 한편보고 다시보니 갑자기 이해가 되었습니다.
아마 오늘 컨디션이 안 좋은 날이었나 봅니다..

풀이법

for (int i = 0; i < n; i++) {
	checked[i] = true;
	num = i;
	dfs(i);
	checked[i] = false;
}

일단 테스트 케이스는 다음과 같다고 해봅시다. 백준에 있는 예시에서 -1만 해준 겁니다.

0	1	2	3	4	5	6
2	0	0	4	4	3	5

이런씩으로 하나씩 index 0~ n까지 돕니다.
여기서 num의 역할이 매우 중요했습니다. 처음에는 왜 쓰는지도 이해가 안되었습니다.
현재 for은 단지 index를 0 ~ n 도는 역할 뿐입니다.

처음으로 DFS를 들가기 전 num에는 0이 들어갑니다. 그런다음 DFS에 들어갑니다.

dfs 진입

public static void dfs(int i) {
	if (arr[i] == num) {
		result.add(i);
	}

	if (!checked[arr[i]]) {
		checked[arr[i]] = true;
		dfs(arr[i]);
		checked[arr[i]] = false;
	}

}

참고로 dfs에 들어오기전에 dfs에 처음에 들어가는 값은 checked가 true가 됩니다.

• checked : true false false false false false false

(괄호 안에 있는 것이 실제 값)

• dfs(0)
  arr(2) == num(0)
  if에서 2번째 index checked가 true가 됩니다.
  checked : true false true false false false false
  그리고 다시 dfs에는 인덱스 arr[0]을 출력하면 나오는 2를 다음으로 넘겨줍니다.
  arr(0) == num(0)
  true입니다. 0을 result에 넣습니다.
  다시 if에서 !checked를 확인합니다. 하지만 들어오기전에 이미 true을 해버렸습니다. 이제 백트래 전부 false을 하면서 나옵니다.
  
• dfs(1)
  이제 num에는 1이 있습니다. 그리고 index 1 checked는 true입니다.
  checked : false true false false false false false
  arr(0) == num(1)
  if에서 0번째 index checked가 true가 됩니다.
  checked : true true false false false false false
  그리고 다시 dfs에는 인덱스 arr[1]을 출력하면 나오는 0를 다음으로 넘겨줍니다.
  arr(2) == num(1)
  checked : true true true false false false false
  arr(0) == num(1)
  if에서 빠져나옵니다. 백트래킹으로 전부 다시 false 시켜줍니다.

이런씩으로 계속 진행되면 집합의 값을 구할 수 있습니다.