16964

[백준] 16964번 DFS 스페셜 저지 풀어보기 [Java]

상대적으로 적은 사람이 푼 문제를 풀어서 뭔가 기분이 좋다. 그리고 오랜만에 1제출 1정답이여서 더 기분이 좋고,,,, 그래프가 주어지고, 해당 그래프를 정점 1 부터 시작해서, DFS로 탐색한 경로가 들어온다. 우리가 찾아야 될 것은 해당 탐색 경로가 DFS로 탐색한 올바른 경로가 맞는지 체크를 하는 것이다. 어느 곳을 먼저 탐색할 지 모르기 때문에, DFS경로는 여러 경로가 나올 수 있다!! 👨‍🏫 풀이 일단, DFS로 진행하여, 해당 그래프의 누가 parent인지 확인을 하고, 자신의 child 수가 몇명인지 확인을 한다. 그리고 입력으로 들어온 Order를 앞에서부터 체크를 한다. 첫 parent는 무조건 1이기 때문에, 1로 설정한다. 현재 순서의 parent와 현재 parent로 설정된 것이 ..