[프로그래머스] Lv3. 양과 늑대 (DFS)

프로그래머스

---

문제 파악

2진 트리 구조의 초원에서 양을 모으는 문제

늑대의 수가 같거나 더 많아서는 안된다.

늑대에게 양이 잡아먹히지 않게 하면서 최대한 양을 많이 모으는 문제이다.

 

제한사항

• 2 ≤ info의 길이 ≤ 17
  • info의 원소는 0 또는 1 입니다.
  • info[i]는 i번 노드에 있는 양 또는 늑대를 나타냅니다.
  • 0은 양, 1은 늑대를 의미합니다.
  • info[0]의 값은 항상 0입니다. 즉, 0번 노드(루트 노드)에는 항상 양이 있습니다.
• edges의 세로(행) 길이 = info의 길이 - 1
  • edges의 가로(열) 길이 = 2
  • edges의 각 행은 [부모 노드 번호, 자식 노드 번호] 형태로, 서로 연결된 두 노드를 나타냅니다.
  • 동일한 간선에 대한 정보가 중복해서 주어지지 않습니다.
  • 항상 하나의 이진 트리 형태로 입력이 주어지며, 잘못된 데이터가 주어지는 경우는 없습니다.
  • 0번 노드는 항상 루트 노드입니다.

입출력 예

info	edges	result
[0,0,1,1,1,0,1,0,1,0,1,1]	[[0,1],[1,2],[1,4],[0,8],[8,7],[9,10],[9,11],[4,3],[6,5],[4,6],[8,9]]	5
[0,1,0,1,1,0,1,0,0,1,0]	[[0,1],[0,2],[1,3],[1,4],[2,5],[2,6],[3,7],[4,8],[6,9],[9,10]]	5

---

접근 방법

기존 트리 탐색에서 인접 노드가 아닌 다른 노드로 탐색하는 방법을 찾아내는 것이 어려웠다.

 

인접 노드를 새로운 리스트에 저장을 해가면서 기존 탐색도 이어가면서 방문했던 노드의 자식 노드들을 탐색하면서 양의 최대값을 구한다.

 

이미지를 그려가면서 탐색 과정을 직접 눈으로 체크했는데 일반적으로는 노란색 글씨처럼 탐색이 되지만 실제로 테스트케이스1을 적용하게 되면 빨간 글씨처럼 노드가 이동하면서 탐색을 진행한다.

 

탐색과정 시각화

코드를 보면서 확인해보자.

---

코드 구현

import java.util.*;

public class Solution {
    static int maxSheep = 0;

    public int solution(int[] info, int[][] edges) {
            // 2진 트리 저장
        Map<Integer, List<Integer>> tree = new HashMap<>();

        for (int[] edge : edges) {
            int parent = edge[0];
            int child = edge[1];

            tree.putIfAbsent(parent, new ArrayList<>());
            tree.get(parent).add(child);
        }

        // 다음 노드를 저장할 리스트
        List<Integer> nexts = new ArrayList<>();
        nexts.add(0);

        dfs(0, 0, 0, info, tree, nexts);

        return maxSheep;
    }

    public void dfs(int cur, int sheep, int wolf, int[] info,
                    Map<Integer, List<Integer>> tree, List<Integer> nexts) {

        // 현재 노드가 양인지 늑대인지 확인
        if (info[cur] == 0) sheep++;
        else wolf++;

        // 늑대의 수가 더 많거나 같으면 종료
        if (wolf >= sheep) return;

        // 최대 양의 수
        maxSheep = Math.max(maxSheep, sheep);

        // 다음 탐색 후보 구성
        List<Integer> newNexts = new ArrayList<>(nexts); // 지금까지 방문했던 후보 노드들
        newNexts.remove(Integer.valueOf(cur)); // 현재 방문 노드 제거

        if (tree.containsKey(cur)) {
            newNexts.addAll(tree.get(cur)); // 자식 노드 추가
        }

        // 다음 후보 노드들에 대해 DFS
        for (int next : newNexts) {
            dfs(next, sheep, wolf, info, tree, new ArrayList<>(newNexts));
        }
    }
}