1. 문제 설명📌(1) 링크🔗  프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr (2) 주목 포인트 🕵1️⃣ 늑대 >= 양 이면 모았던 양의 개수가 0이 된다!2️⃣ 현재 특정한 서브 트리를 방문 중이라 가정할 때, 해당 트리에서 최대 이익을 이미 냈다고 확신한다면, 조상 노드를 거슬러 올라가 다른 서브 트리를 파고 드는 것이 가능하다.2. 생각의 흐름: 코드가 나오기까지 🗃️(1) IDEA 도출💡KEY WORD: BACK-TRACKING, DFS해설에서 설명한 2️⃣번째 포인트 때문에, 이번 문제는 BACK-TRACKING에 가깝게 변형된 DFS를 사용해야 한다. 깊이 우선 탐색을 하는 성질은..

1. 문제 설명 📌문제 링크정점 1 ➜ 정점 N으로 갈 건데, 이 둘 사이에 특정한 정점 A, B를 꼭 거쳐야 한다. 이 특정한 정점 2개를 꼭 거치면서 갈 수 있는 최단 경로의 비용을 구하여라2. 구현 방법 🗃️KEY WORD: DIJKSTRA특정 정점 A,B를 꼭 거치면서, 1 ➜ N 까지 가는 최단 경로는 다음 2가지 중 하나 일 것이다.1 ➜ A, A ➜ B, B ➜ N 각각의 최단 경로를 구해서 합한다.1 ➜ B, B ➜ A, A ➜ N 각각의 최단 경로를 구해서 합한다.이게 가능한 이유는 모든 가중치가 양수이기 때문이다. A,B로 가는 부분적인 최단 경로에서 벗어나는 정점을 방문하는 것 자체가 비용을 늘릴 뿐 도움되지 않는다. 따라서 각각 부분적인 최단 경로의 합이 곧 전체 최단 경로가 될..