2022 Kakao blind 92343 - 양과 늑대(트리, 백트래킹 or dp) - Java, C++ 풀이

https://programmers.co.kr/learn/courses/30/lessons/92343

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

- 방문한 노드를 또 방문할 수 있고 노드의 갯수 n = 17이기 때문에 17^17 완전탐색을 할 수 없다. 
방문한 노드는 다시 방문하지 않으면서 현재 노드에서 방문가능한 노드를 메모이제이션 하면서 재귀적으로 방문하는 백트래킹 방식으로 풀었다. 비트마스킹을 사용할 수도 있는데 풀이에서는 해쉬셋을 이용했다. 

- 몰랐던 내용인데 문제 상에서 주어진 이진트리가 complete binary tree일 경우에는 백트래킹을 이용하면 메모이제이션을 이용해도 시간초과가 나지만 TC가 빈약해서 통과된 문제라고 한다. (이진 트리이므로 탐색순서가 달라도 이미 방문한 노드가 같은 경우의 수가 존재함. 메모이제이션한 값이 중복되는 경우의 수가 무조건 존재함)
따라서 무조건 서브트리에 대하여 최적화해나가는 방식의 tree dp만이 정해가 될 수 있다. 

- 경로를 메모이제이션하게 되면 따로 재귀적으로 값을 넘길 필요 없이 방문한 노드에 대한 늑대와 양 존재여부를 알 수 있다(카운트를 할 수 있다). 트리dp 방식은 본인이 dp문제 풀때 익숙한 C++로 풀었다. 

 

import java.util.*;

class Solution {
    List<Integer>[] a = new ArrayList[17];
    int ans = 1;
    
    public int solution(int[] info, int[][] edges) {
        for(int i = 0; i < 17; ++i) {
            a[i] = new ArrayList<>();
        }
        for(int[] e: edges) {
            int u = e[0], v = e[1];
            a[u].add(v);
        }
        
        dfs(0, 0, 0, new HashSet<Integer>(Arrays.asList(0)), info);
        return ans;
    }
    
    void dfs(int now, int sheep, int wolf, Set<Integer> cango, int[] info) {
        if(info[now] == 0) ++sheep;
        else ++wolf;
        
        if(wolf >= sheep) return;
        if(ans < sheep) ans = sheep;
        
        Set<Integer> nextcango = new HashSet<>(cango);
        nextcango.remove(now);
        
        for(int next: a[now]) {
            nextcango.add(next);
        }
        
        for(int next: nextcango) {
            dfs(next, sheep, wolf, nextcango, info);
        }
    }
}

#include <vector>
#include <cstring>
using namespace std;

bool a[17][17];
int d[17][1 << 17]; // d[now][route] = route를 거쳐 now도착시 양의 최대값

int go(int now, int route, vector<int>& info) {
    int& ret = d[now][route];
    if(ret != -1) return ret;
    ret = 0;
    
    int sheep = 0, wolf = 0;
    for(int i = 0; i < 17; ++i) { // 거쳐온 경로 늑대, 양 체크
        if(route & (1 << i)) {
            if(info[i]) ++wolf;
            else ++sheep;
        }
    }

    if(sheep <= wolf) return ret;
    
    ret = sheep;
    for(int i = 0; i < 17; ++i) {
        if(!a[now][i]) continue;
        ret = max(ret, go(i, route | (1 << i), info));
    }
    
    return ret;
}

int solution(vector<int> info, vector<vector<int>> edges) {
    for(vector<int>& e: edges) {
        int u = e[0], v = e[1];
        a[u][v] = a[v][u] = true;
    }
    memset(d, -1, sizeof(d));
    return go(0, 1, info);
}