문제 : https://school.programmers.co.kr/learn/courses/30/lessons/92343
🚨 오늘의 학습
⭐️ 백트랙킹 ⭐️
해를 찾는 도중 해가 절대 될 수 없다고 판단되면, 되돌아가서 해를 다시 찾아가는 기법 ▶️ 양<늑대인 경우 해가 될수 없으므로 다른 경로 찾아야함
⭐️ Tree(트리) ⭐️
- 그래프의 일종으로 정점과 간선을 이용하여 데이터의 배치 형태를 추상화한 자료구조
- 트리의 구조는'저장된 데이터를 더 효과적으로 탐색'하기 위해서 사용된다.
- 부모-자식의 관계를 가지는 계층적 구조로 단 하나의 부모노드를 가진다.
- 트리는 사이클이 없다
🗝️ 트리 자료구조를 어떻게 표현할 것인가?
🗝️ DFS를 통한 백트랙킹 (초기화 🅾️ → 다른 경로에 영향을 미치지 않게 하기 위해서)
HOW...❓
🤔 트리 VS 그래프
✅
Q. 노드의 방문여부 관리 필요한가? -> ❌
A 재방문하는 경우 허용해야함
Q. 재방문을 허용하려면?
A. 방문여부 확인X, 노드와 연결된 자식노드로 관리
Q. dfs 종료조건은?
A. 양의수<= 늑대 수
🔎 풀이
-
입력
info[] = 노드별 양/늑대 정보
edge = 노드의 연결정보 -
로직
모든 노드를 탐색하여 최대의 양을 구한다
전역 양의수 = 0;
1.dfs(현재 노드, 자식 노드 ,양의수, 늑대수)1-1-1.if(양<=늑대) 종료
1-1-2. 전역 양의수 = Math.Max(전역,양의수)
1-1-3. 자식 노드 복사
1-1-4. 자식 노드에서 현재 노드 제거
1-1-5. 자식 노드에 현재 노드의 자식 노드 추가
1-1-6. info==0 -> 양+1 / 늑대 +1
1-1-7. 모든 자식 노드를 방문 DFS -
출력
양의 수 최대값
with me