백준 16964 자바 - DFS 스페셜 저지 (BOJ 16964 JAVA)

문제 링크 : https://www.acmicpc.net/problem/16964

코드 링크 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/16900/BOJ_16964.java

 

 

  해결 방식을 떠올리기 다소 어려웠다. 결국 올바른 DFS 방문 순서라 함은 '각 간선을 방문하는 순서는 상관없지만 어쨌든 방문할 간선이 남아 있다면 무조건 방문해야 한다.' 이걸 지키면된다.

 

예를 들어 아래와 같은 그래프를 보자. 1부터 시작한다. 방문한 곳은 빨간색으로 표시했다.

 

1에서 2부터 가야할까 3부터 가야할까? 상관없다. 우선 2로 가보겠다.

 

이 때, 3을 가면 올바른 DFS 순서가 아니게 된다. 2로 일단 갔으면 2에 연결된 간선을 모두 들린 후 3으로 갈 수 있다. 우선 5로 가보겠다.

 

여기서도 마찬가지로 4를 남긴채로 3으로 가면 올바른 DFS 순서가 아니다. 무조건 4로 가야 한다. 또 하나의 주의점은 1 다음에 3보다 2를 선택했다고, 무조건 간선 중 다음 노드가 낮은 숫자를 선택해야 하는 것은 아니다. 간선 중 어떤걸 선택해도 상관없다. 즉 위 과정에서 1->2->4->5를 했어도 올바른 DFS 순서이다.

 

이제 마지막으로 3을 들리면 된다.

 

  

 

  그럼 문제를 풀기위해 입력에 들어온 DFS 순서를 어떻게 판단해야 답을 구할 수 있을까?

위의 과정에서 1에서 3보다 2를 먼저 들렸고, 2에서는 5를 4보다 먼저 들렸었다. 또 1->3->2->4->5 처럼 진행해도 올바른 순서인데, 이 경우엔 1에서 2를 먼저 들리고 2에서는 4를 먼저 들린다. 이러한 경우를 완전탐색으로 탐색해서 문제의 입력과 동일한 순서가 있는지 찾는 것은 당연하게도 시간초과를 초래한다.

 

 

1. 첫째로 중요한 것은 '문제의 입력에서 각 정점에서는 어떤 순서로 간선을 방문했냐' 이다. 이 부분은 입력으로 들어온 DFS 방문 순서대로 각 정점의 간선을 정렬해주면 된다. 들어온 정점번호의 순서(코드의 target)대로 renumbering을 통해 순서 배열(코드의 order)을 만든다. 마치 좌표압축할 때 순서대로 번호를 주는듯이 하면 된다.(ps. 이 문제처럼 13711번 LCS 4도 renumbering을 하면 상당히 쉬운 문제가 된다.) renumbering에 대한 개념은 떠올리기 쉬운 개념은 아니므로 아마 골4에서 더 올라갈 것 같다.

 

예를들어 입력으로 들어온 DFS 방문순서가 '1 5 2 4 3' 이라면 아래와 같이 된다.

그럼 이제 order 배열을 기준으로 각 정점의 간선들을 정렬하면 각 정점에 대해 입력으로 제시된 순서와 동일한 순서로 방문하며 확인할 수 있게 된다.

 

 

2. 다음으로 '방문할 간선이 남았는데도 탐색에서 해당 간선을 탐색하지 않은 경우'는 어떻게 파악할 수 있을까? 스택같은걸 사용해서 실제로 검사를 해봐도 되겠지만, 더 쉬운 방법이 있다! '1'에서 계산해둔 간선 방문 순서대로 직접 DFS를 돌려보는 것이다. 결국 간선 방문 순서가 확정되었다면, DFS를 몇 번 돌리든지 동일한 답이 나와야 한다. 따라서 DFS를 실제로 돌려보고 하나씩 확인하면서(코드에서 idx를 증가시키면서 확인함) 문제에서 입력된 값과 다른 값이 발견된다면 해당 입력은 틀린 것(0)이고, 실제 DFS 돌린게 문제 입력과 동일하다면 올바른 순서로 방문한 것(1) 이다.