[백준 2668번] 숫자고르기 - java

문제 설명

1. 세로 두줄, 가로 N칸짜리 표가 주어진다.

2. N에 해당하는숫자들이 주어진다.

3. 0번Line숫자 -> 1번Line숫자 ->0번Line숫자 로 돌아오는 숫자들을 오름차순으로 출력한다.

풀이 과정

 1. DFS와 Prority Queue를 이용하여 풀이한다.

 2. 문제의 주요 골자는 map에 각 숫자를 적어두고 map[i]와 map[map[i]] 이런 식으로 함수를 쭉쭉 돌리면서 자기 자신의 숫자가 나타나면 되는 것이다.

1	2	3	4	5
3	5	1	5	1

map[1] = 3, map[map[1]] = 3  

 

 3. DFS에서 값들을 체크하면서 i -> map[i] -> map[map[i]] -> map[map[map[i]]] ..... 이렇게 도달하지 않은 곳까지 체크한다.

 4. 자기 자신이 나오는 순간 해당 위치의 숫자를 저장한다.

 5. 이를 Priority Queue에 담으면 바로 오름차순 배열이 가능하다.

 6. 생각보다 쉬울 줄 알았는데 난이도가 있는 문제였다... DFS구현 자체보다는 알고리즘 생각에 조금 더 시간을 투자해야 할 것 같다.

코드