[Java] 양과 늑대

문제 접근법 정말 낯선 유형의 탐색문제였다. 보통 DFS나 BFS 같은 탐색 문제를 풀때, 이전 경로로 돌아갔다가 다시 방문했던 노드를 가는 경우는 한번도 푼적이 없었기에 구현을 생각하는게 너무 머리아팠다. 결국 오랜 고민끝에 구글링을 해보았고, 백트래킹 방식으로 풀었다는 것을 알게 되었다. 위의 예제에서 트리 구조를 List로 표현하면, 다음과 같다. 0: 1,8 1: 2, 4 2: 3: 4: 3, 6 5: 6 6: 7: 8: 7, 9 9:10, 11 0번 노드에서 방문할 수 있는 노드는 1, 8이다. 이를 저장해두고, 다음 두가지를 생각한다. 1번 노드를 방문했을 경우 8번 노드를 방문했을 경우 1번 케이스 다음 경로 - [8, 2, 4] 2번 케이스 다음 경로 - [1, 7, 9] - 이 경우는 "늑대 >= 양"의 케이스이므로 더 이상 탐색하지 않게 된다. 중요한 포인트는 만약 특정 노드에 도착했으나 늑대가 더 많아 방문하지 못했다고 하더라도, 그 노드를 살려두어 나중에라도 방...

원문링크 : [Java] 양과 늑대