[JAVA] 백준 16964번 DFS 스폐셜 저지

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

16964번: DFS 스페셜 저지

이 글을 기재하는 이유는 그래프 탐색 알고리즘인 DFS와 BFS 개념에 대해 스스로 정리하기 위해서 이며,

알고리즘 로직을 잘못 짰을때 찾았던 반례와 잘못 생각했던 부분을 기록하여 나중에 잊어버리더라도 다시 생각하기 위해서이다.

 

우선, DFS란 그래프를 탐색하는 알고리즘 중에 하나이며 Depth First Search, 깊이 우선 탐색이다.

루트노드 또는 임의의 노드에서 다음 분기로 넘어가기 전까지 해당 분기를 완벽하게 탐색하는 알고리즘이다.

모든 노드를 탐색할 때 사용하는 알고리즘으로, 주로 자기 자신을 호출하는 재귀함수로 구현한다.

이때, 탐색한 노드를 반드시 표시해주어야 한다.

 

그래프를 탐색하는 다른 알고리즘은 BFS, Breadth First Search 너비우선 탐색이다. (Breath=숨 아니다)

시작정점으로부터 가장 가까이에 있는 노드를 먼저 방문하는 알고리즘이다.

방문한 노드를 차례로 꺼낼 수 있는 Queue 자료구조를 사용한다.

최단거리를 구하는 문제에서 주로 사용된다.

 

16964번은 트리형식의 그래프를 DFS로 노드를 방문했을 때, 방문순서가 맞는지 확인하는 문제이다.

아래는 내가 풀었던 방식이다.

내 코드를 공개하는건 뭔가 부끄러운 것 같다.. (어차피 나만 볼 것 같다)

 

나는 dfs 방식으로 방문한 순서가 맞는지 확인하기 위해서 HashSet을 사용했다.

문제에서 주어진 dfs 방문 순서는 int[] order 배열에 데이터를 저장하고,

index를 0부터 차례로 탐색하면서 set에 데이터를 넣어준 뒤 order[index]의 데이터와 일치한게 있으면 재귀함수를 호출하여 노드를 방문했다고 표시한 후 다음 탐색을 하고, set에서는 데이터를 삭제해줬다. order[index]의 데이터와 일치하지 않으면 set에 데이터를 넣어주고, 다음 노드가 일치하는지 확인했다.

order[index]와 일치할 때마다 cnt 숫자를 늘려주면서, order[index+cnt]로 표기하여 현재의 순서를 기억했고,

최종 index가 n이면 dfs 순서가 맞는 것으로 봤다. 이렇게 했더니 통과했다..

 

처음에는 Stack을 사용했다. stack에 보관했다가 order[index]와 동일하면 다음탐색을 하고 stack에서 빼줬다.

하지만..! 그렇게 하면 노드에 연결된 자식노드가 여러개일때, 순서가 동일하지 않을 수 있다는 것을 간과했다... (6%에서 틀렸습니다 뜸)

예를들어, 7개의 노드가 1-2, 1-3, 1-4, 1-5, 1-6, 1-7 로 연결되어있을때 stack에 넣는 순서대로 dfs 방문을 탐색하지 않을수도 있는데... 

그래서 set으로 변경했더니 통과...

 

 

백준쌤의 정답을 확인했는데, 더 간편한 풀이법이 있었다.

 

각 트리의 정점과 정점의 연결을 list에 담는다. → list[u].add(v), list[v].add(u)

각 노드가 방문하는 순서를 배열에 담는다. → order[노드번호] = dfs 탐색 순서.

예를들어, 1번 노드가 1번째이면 order[1] = 1, 6번 노드가 2번째이면 order[6] = 2, 3번 노드가 3번째이면 order[3] = 3...

그리고 list[u]를 order[u]순서로 정렬을 해준다! → 먼저 방문한 노드가 앞으로 가게 정렬이 된다.

이렇게 정렬이 된 상태에서 dfs 함수를 호출을 하고, 문제에서 주어진 dfs 방문 순서와 비교를 해서 동일하면 정답!

 

다음에 이와 같은 문제를 푼다면,

for(int i=0; i<n; i++) {

     Collections.sort(list[i], new Comparator<Integer>() {

          @Override

          public int compare(Integer u, Integer v) {

               return order[u]-order[v];

          }

     });

}

 

위 코드를 꼭 써서! 정렬을 해서 쉽게 풀어야겠다.