자문자답 하겠습니다.
인접 정점 리스트에 대해서 BFS 의 경우 오름차순 정렬, DFS 의 경우 needVisit 를 스택으로 만들 것임을 고려해서 내림차순 정렬을 해주었는데요
리스트에 대한 정렬을 수행함에 있어서 PriorityQueue 클래스(우선순위 큐)로 만든 객체에 모든 것을 맡겼더니
어떤 이유에서 인지 아직 잘 모르겠지만 특정 입력이 들어왔을 때 정렬을 제대로 해주지 못하고 있던 것을 발견했습니다.
찾아낸 반례는 다음과 같습니다.
4 3 1 1 2 1 3 1 4 ---- 1 2 3 4 1 2 3 4
이 경우 두번째 줄에 BFS 탐색 결과를 출력하는데 있어서 1,2,3,4 가 아니라 1,2,4,3 을 내뱉고 있길래
정점 1 과 연결된 인접 정점 리스트의 상태를 확인해봤더니, PriorityQueue 클래스로 큐를 만들었음에도 불구하고 [2,4,3] 과 같이 제대로 정렬을 해주지 못하고 있는것을 발견할 수 있었습니다.
일단 우선순위 큐 클래스가 힙 자료구조를 이용해서 데이터를 정렬 해준다는것은 알고 있으나 그럼에도 불구하고 왜 그동안 잘 해주던 정렬을 갑자기 이상하게 해주는건지는 아직 잘 모르겠습니다만, 그럼에도 불구하고 일단 해결은 했습니다.
우선순위 큐 사용을 배제하고 List<Integer> 클래스를 활용하여 인접 정점 리스트를 만들어준 다음,
BFS 일 경우 Collections.sort() 를 통한 오름차순 정렬, DFS 일 경우 Collections.sort(리스트, Collections.reverseOrder()) 를 활용한 내림차순 정렬을 해주었더니 무사히 통과할 수 있었습니다.
아래는 소스 코드 전문 입니다.
ghwns6659 2년 전
정점과 인접 정점 리스트를 저장하는 자료구조로는 해시맵을 썼고, 갈 수 있는 정점이 여러개 있을 경우 숫자가 작은 노드부터 가게끔 하기 위해 인접 정점 리스트를 우선순위 큐로 구성했습니다.
DFS 같은 경우엔 스택으로 needVisit 을 만드는걸 고려해서 인접 정점 리스트를 내림차순으로 정렬했구요
입력을 뒤집어서 다시 해시맵에 넣는 이유는, 기존 테스트 케이스에서 첫번째걸 보니까 정점 4를 기준으로 연결된 정점을 찾으려면 다른 정점들에 4가 연결되어 있는걸 직접 찾아서 넣어줘야 하다 보니까 그렇게 작성해 놓았습니다.
기존에 제공되어 있는 테스트 케이스도 답이 잘 나오고, 몇 가지 다른 사람들이 찾은 반례를 찾아서 돌려봐도 답 자체는 잘 나오는데
어떤 부분에서 틀린점이 있는걸까요....?
코드가 조금 더러운 느낌이라 죄송합니다;;;