(JAVA) 백준 2668번 : 숫자고르기 --- [완전탐색]

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

2668번: 숫자고르기

 

안녕하세요.

 

DFS 관련 문제 입니다. (완전탐색 느낌도 있음)

 

 

이 문제를 푸는데 오래걸렸습니다.

 

풀이 방법은 떠올랐는데, 예외에 대한 처리를 하지 못하는 상황이어서

 

결국 해설을 조금 참고했었습니다.

 

 

 

이 문제의 핵심은 바로 사이클 입니다.

 

첫 번째 카드들은 1,2,3 ... n 이렇게 순차적이고, 두 번째 카드들은 임의의 1~n 까지 숫자 입니다.

첫 번째 카드들 중 뽑은 숫자들과 뽑은 숫자들과 쌍을 이루는 두 번째 카드들의 숫자 집합은 같아야 합니다.

 

 

이 조건에 따라 처음에 한 번 for문으로 순회하면서 첫 번째 카드의 수 = 두 번째 카드의 수 인 카드들을 찾습니다.

 

그래서, 해당 index 번 째 카드를 뽑았는지 안뽑았는지 체크하는 boolean 배열을 만들어

위 조건에 맞는 카드들을 true로 바꿉니다.

 

즉, 먼저 첫 번째 카드의 수 = 두 번째 카드의 수 인 카드를 뽑아두는 것이죠.

 

 

다음, for문으로 순회하면서 첫 번째 카드를 하나씩 뽑습니다.

 

그래서 뽑은 카드의 쌍인 두 번째 카드의 값을 확인하고,

그 값을 인덱스로 하는 첫 번째 카드를 확인합니다.

 

그렇게 파도파도 타면서 쭉 진행하는데, 이 때 맨처음 뽑았던 첫 번째 카드의 값과 두 번째 카드의 값이 일치하면 사이클!

 

 

매커니즘

---

예를 들어,

 

첫 번째 카드 :  1  2  3  4  5

두 번째 카드 :  3  2  1  4  5  

 

일 때, 값이 1인 첫 번째 카드를 먼저 뽑았다고 하면

 

1)

첫 번째 카드 :  1   2   3   4   5

                     1)↓

                     1)↓

두 번째 카드 :  3   2   1   4   5  

 

 

2)

첫 번째 카드 :  1   2   3   4   5

                         2)↗

                     2) ↗

두 번째 카드 :  3   2   1   4   5  

 

 

3)

첫 번째 카드 :  1   2   3   4   5

                             3)↓

                             3)↓

두 번째 카드 :  3   2   1   4   5  

 

 

3)

첫 번째 카드 :  1   2   3   4   5

                             3)↓

                             3)↓

두 번째 카드 :  3   2   1   4   5  

 

 

4)

첫 번째 카드 :  1   2   3   4   5

                      4)↖

                          4)↖

두 번째 카드 :  3   2   1   4   5  

  ->  앗! 이미 뽑았던 카드네? (항상 뽑기 여부 체크해서 뽑지 않은 카드만 찾아 뽑는다.)  ====> 탐색 종료.

  ->  앗! 두 값이 같네 ====> 사이클이다! ====> 최대 개수는 2개 뽑았으니까 2다!

*** 근데, 뒤에 4와 5는 같은 값을 가지는 카드 쌍이므로 어차피 뽑아두고 있어도 되는구나! 그럼 2개를 추가해서 최대 개수는 4개!

 

 

이렇게 접근해서 풀었습니다.

 

여기에서 완전탐색을 사용하는 이유는

 

만약 저렇게 파도파도 타다가 끝에가서 사이클이 아니면

 

뽑았다는 흔적을 지워야 하기 때문에

 

 

뽑았다!  ->  파도파도 타자!  ->  안뽑았다로 바꾸자!

 

로 코딩해야 합니다.

 

 

즉,

checked[ele] = true;
getCycle(ele, last, n);

if(!isCycle) {
checked[ele] = false;	
}

이런 방식으로 코딩해야 되돌릴 수 있습니다.

 

그래서 별도 boolean 변수를 통해

 

사이클이면 뽑은 흔적을 그대로 두고

사이클이 아니면 false로 변경해서 뽑은 흔적을 없애야 합니다.

 

 

 

나머지 더 궁금하신 사항이나 자세한 것을 알고 싶으시면 하단 소스코드를 참고해주세요.

댓글도 부탁드립니다.

 

감사합니다!

 

소스코드

---