BOJ 16964 DFS 스페셜 저지

16964번: DFS 스페셜 저지

 

일반적인 DFS가 아닌, 주어진 입력이 DFS 탐색했을 때 올바른 입력인가? 를 판정하는 문제이다.

요 근래 들어가 가장 많은 시도 끝에 정답을 띄운 문제였던 것 같다.

결국 알고리즘 자체는 DFS라 간단하지만, 아이디어를 내는 것이 어려운 문제였다.

 

 

 

---

일반적으로 트리에 노드를 삽입할때, 특정한 기준을 둔다.

 

다시 말해 자식 노드 두 개 있을 때

• 더 작은 노드가 앞에오게 하거나 (= 오름차순 정렬)
• 더 큰 노드가 앞에 오게 하거나 (= 내림차순 정렬)
• 더 먼저 들어온 노드가 앞에 오게 하거나
• 더 늦게 들어온 노드가 앞에 오게 하거나
• 필요에 의한 또 다른 기준 (ex 절댓값 순서 등이 가능)에 의해 앞에 오게 하거나

등 특정한 기준을 두고 트리를 구성하게 되는데, 이 문제에서는 그 기준을 마지막 줄에 입력되는 DFS 방문 순서에서의 등장 순서를 가중치로 두면 된다.

 

 

 

그 뒤, 1번 노드에서 시작하는 트리를 그리면 된다.

단 이때 2개 이상의 노드를 자식으로 갖는 경우 가중치가 낮을수록 왼쪽에 위치하도록 구성한다.

 

 

 

 

다른 예시인 1 3 2 4 를 이용해서 동일하게 트리를 만들어보면 아래와 같다.

 

 

 

이렇게 만들어진 트리의 전위 순회 결과와 입력된 DFS 방문 순서가 일치하는지 확인하면 된다.

 

---

code

GitHub - YoungWoo93/algorithmOnlineJudge: 알고리즘 온라인 저지