Kakao 2022 Blind Test - Lv3. 양과 늑대 (Java)

문제 요약

2진 트리 모양인 초원의 각 노드에 양과 늑대가 한 마리씩 놓여있다. 루트노드에서 출발하여 각 노드를 돌아다니며 양을 모을 때, 최대로 모을 수 있는 양의 개수는?

 

[문제 설명] 

• 2진 트리의 각 노드를 방문하여 양과 늑대를 모은다.
• 모아진 늑대의 개수가 양의 개수보다 많거나 같을 때, 늑대는 양을 모두 잡아 먹는다.
• 각각 연결된 노드들을 다양한 순서로 방문하여 최대로 모을 수 있는 양의 개수를 구하라. 

 

[제한 사항]

1. info: 노드의 정보 (0: 양, 1: 늑대) (2 ≤ info의 길이 ≤ 17) / info[0]은 항상 0이다.
2. edges: 서로 연결된 노드 정보 (세로 행의 길이 = info의 길이 - 1, 가로 행의 길이 = 2) 

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

 

---

문제 접근 

• 깊이우선탐색(dfs)을 사용
• 방문 순서에 따라 늑대가 양을 잡아 먹을 수도, 잡아먹지 않을 수도 있기 때문에 모든 경우의 수를 탐색
• 다만, 현 노드 시점에서 자신을 포함해 늑대와 양의 수를 계산했을 때, 늑대 수가 양보다 많을 때는 더이상 트리를 탐색하지 않는다. 
  • 양이 늑대를 잡아먹어 양의 수가 최대임을 보장하지 못한다.

자세한 접근 법은 코드의 주석을 확인하세요 🙂

import java.util.*;

public class Solution {

    public static void main(String[] args) {
        int result = solution(new int[]{0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0},
                new int[][]{{0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 5}, {2, 6}, {3, 7}, {4, 8}, {6, 9}, {9, 10}});
        System.out.println(result);
    }

    static ArrayList<Integer>[] tree;
    static int max = Integer.MIN_VALUE;

    public static int solution(int[] info, int[][] edges) {
        tree = new ArrayList[info.length];

        for (int[] edge : edges) {
            int parent = edge[0];
            int child = edge[1];
            if (tree[parent] == null) {
                tree[parent] = new ArrayList<>();
            }
            tree[parent].add(child);
        }

        // visit 라는 boolean 배열로 방문을 처리하지 않고 방문할 노드를 담고 있는 리스트를 만든다
        List<Integer> visit_list = new ArrayList<>();
        // 본격적으로 탐색을 시작하기 전, 현재 노드 0 (루트)를 방문할 노드에 추가한다.
        visit_list.add(0);
        // 탐색을 시작한다.
        dfs(0, 0, 0, visit_list, info);
        return max;
    }

    private static void dfs(int current, int sheep, int wolf, List<Integer> visit_list, int[] info) {

        // 방문할 노드가 양이라면 양의 수를 1 증가시킨다.
        // 반대의 경우 늑대의 수를 1 증가시킨다.
        if (info[current] == 0) sheep++;
        else wolf++;


        // 만약 현재 노드 시점에서 늑대의 수가 양의 수보다 많다면 더이상 탐색하지 않는다.
        if (wolf >= sheep) return;

        // 만약 현재 노드 시점에서 양의 수가 최대 양의 수보다 많으면 값을 갱신한다.
        max = Math.max(sheep, max);

        // visit_list를 복사하지 않고 쓸 경우, 같은 객체를 가리켜 visit_list의 값이 훼손될 수 있다.
        List<Integer> copied_list = new ArrayList<>();
        copied_list.addAll(visit_list);
        // 자식노드가 있다면 방문 리스트에 추가시킨다.
        if (tree[current] != null) {
            for (int each : tree[current])
                copied_list.add(each);
        }
        // 현재 탐색하려는 노드는 방문 리스트에서 제거한다.
        copied_list.remove(Integer.valueOf(current));

        // 차례대로 노드들을 방문한다.
        for (int next : copied_list) {
            dfs(next, sheep, wolf, copied_list, info);
        }
    }
}

---

느낀점

처음 탐색할 때, 중복 방문을 줄이기 위하여 방문하는 노드까지 가질 수 있는 최대 양의 개수를 memoization하는 방법을 생각했다.

그러나 방문 순서에 따라 방문하는 노드 시점에서 가질 수 있는 양의 최대 개수가 달라지기 때문에 memoization이 필요하지 않을 것이라 결로 내렸다. 이때 문제는 많은 dfs로 인해 재귀의 중복이 많아진다는 것인데, 중복의 수를 줄이기 위하여 늑대와 양의 수가 같다면 더이상 탐색을 진행하지 않는 조건을 추가하였다. 

 

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/92343

코딩테스트 연습 - 양과 늑대