[프로그래머스] 92343 - 양과 늑대 (Java)

로고를 클릭하면 문제 페이지로 이동합니다.

---

 

 

문제 설명

이진 트리 모양의 각 노드에 늑대와 양이 한 마리씩 놓여 있고, 이 트리의 루트 노드에서 출발해서 각 노드를 돌아다니며 양을 모으려고 합니다. 각 노드를 방문할 때마다 해당 노드에 있던 양이나 늑대가 나를 따라오는데, 이 때 모은 양의 수보다 늑대의 수가 같거나 더 많아지면 모든 양이 잡아먹힙니다.

최대로 모을 수 있는 양의 수를 구합니다.

• 루트 노드에는 항상 양이 위치
• 잘못된 입력이 주어지는 경우는 X
• 2 <= 노드의 수 <= 17

풀이

첫 번째 풀이

아이디어

노드의 수가 최대 17로 작기 때문에 완전탐색으로 풀이했습니다.

코드 (Java)

결과 (Java)

 

두 번째 풀이

아이디어

dfs 풀이인데 굳이 부모 노드로 돌아가는 로직을 직접 넣을 필요가 없었습니다. 또한, 아예 다음에 갈 수 있는 노드 목록을 넘겨 불필요한 재귀가 일어나지 않도록 수정했습니다.

코드 (Java)

결과 (Java)