[프로그래머스 lv3] 양과 늑대 풀이

해당 문제는 2022 KAKAO BLIND RECRUITMENT 출제 문제로 공식 해설이 있습니다.

2022 카카오 신입 공채 1차 온라인 코딩테스트 for Tech developers 문제해설

 

 

해설

주어진 노드 개수 범위가 크지 않기 때문에 모든 루트를 완전탐색하여 해결할 수 있다.

 

func(int cur, int nlamb, int nwolf, vector<int> vnext) 

(cur: 현재노드, nlamb: 현재노드까지 양의 수, nwolf: 현재노드까지 늑대의 수, vnext: 다음으로 이동할 수 있는 노드 후보) 라 할 때, 

 

1) nlamb <= nwolf 이면 양이 늑대에게 모두 잡아먹히므로 이동을 종료한다.

2) 잡아먹히지 않았다면, nlamb의 최댓값을 기록한다.

3) 이제 vnext에 들어있는 노드 중 하나를 선택하여 다음 노드로 넘어가야 하는데, 다음 노드로 넘어가기 전 vnext에서 다음 노드를 제거해야 한다. 대신, 다음 노드의 자식노드를 추가하여 다음노드로 이동했을 때의 후보 노드를 완성한다. 

4) 다음 노드에 양이 있다면 nlamb에 1을 추가하고, 늑대가 있다면 nwolf에 1을 추가하여 다음노드로 이동한다.

 

해당 과정을 재귀적으로 반복한 뒤, 기록된 nlamb의 최댓값을 리턴하면 정답이다.

 

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

int mx;
vector<vector<int>> child(20, vector<int>(0));

void setGraph(const vector<int>& info, const vector<vector<int>>& edges) {

    for (auto v : edges) {
        int p = v[0];
        int c = v[1];
        child[p].push_back(c);
    }
}

void func(const vector<int>& info,int cur, int nlamb, int nwolf, vector<int> vnext) {

    if (nlamb <= nwolf) return;
    mx = max(nlamb, mx);

    for (auto next : vnext) {

        vector<int> tmp = vnext;
        tmp.erase(find(tmp.begin(), tmp.end(), next));
        for (auto x : child[next]) tmp.push_back(x);

        if (info[next]) func(info, next, nlamb, nwolf+1, tmp);
        else func(info, next, nlamb+1, nwolf, tmp); 
    }
}

int solution(vector<int> info, vector<vector<int>> edges) {

    setGraph(info, edges);

    vector<int> vnext;
    for (auto x : child[0])
        vnext.push_back(x);

    func(info, 0, 1, 0, vnext);
    return mx;
}