코드와 관계없이 문제에 관한 질문부터 하겠습니다.

1부터 10까지 노드가 있을 때, 4 뒤에 6이 와야한다는 조건만 있을경우

노드를 6을 빼고 나머지를 순서대로 출력한뒤, 6이 맨 마지막에 와도 정답인지 궁금합니다.

만약 그게 맞다면 제 풀이 방식에 대한 질문도 하고싶습니다.

우선 저는 Union Find 에서 사용하는 방향 그래프를 활용하여 풀어보았습니다.

코드의 원리는 A 다음 B가 와야할 때, arr[B] = A; 라고 해줌으로써 B의 부모가 A임을 저장했고요,

1. 부모가 없는 노드들(이하 root)을 먼저 출력을 다 해주고, queue 에 push

2. queue를 따라가며(root 노드들) 그의 자식을 찾아서 root들이 push 됐던 queue에 push 후 노드의 연결 해제

3. 반복

이라는 알고리즘을 세웠는데요.

이게 처음 질문의 답이 맞다라고 하면 이론상 맞아야한다고 생각하는데, 문제가 채점되기도 전에 바로 틀려버리니까 무슨 반례라도 있는지 찾아봤는데 제대로 찾지를 못하겠습니다.

반례를 아무리 찾아보고 입력을 넣어봐도 정상적인 출력이 나옵니다.

고수분들 도와주시면 정말 감사하겠습니다.

읽어주셔서 감사합니다.