[C++] Programmers 양과 늑대 (2022 KAKAO Blind Recruitment)

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

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

신박하게 풀 여러가지 방법을 떠올려봤지만, 모두 완전탐색 방식보다 코드가 지저분해지길래 포기했다. 

#include <string>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

vector<vector<int>> graph;
vector<int> info_g;

int ans = 0;

void DFS(int cur, int sheep, int wolf, queue<int> q) {
    
    if (info_g[cur] == 0) {
        sheep++;
    } else {
        wolf++;
    }
    
    if (wolf >= sheep) return;
    if (ans < sheep) ans = sheep;
    
    // add new candid
    for (int i = 0; i < graph[cur].size(); i++) {
        q.push(graph[cur][i]);
    }
    
    for (int i = 0; i < q.size(); i++) {
        int next = q.front();
        q.pop();
        DFS(next, sheep, wolf, q);
        q.push(next);
    }
}


int solution(vector<int> info, vector<vector<int>> edges) {
    int n = info.size();
    
    graph.assign(n, vector<int>({}));
    info_g.assign(info.begin(), info.end());
    
    for (int i = 0; i < n-1; i++) {
        int pi = edges[i][0];
        int ci = edges[i][1];
        graph[pi].push_back(ci);
    }
    queue<int> q;
    DFS(0, 0, 0, q);
    return ans;
}

가장 직관적으로 모든 순서를 다 돌아가도록 코드를 작성하였다. 일반적인 DFS과 다른 점은 보통 현재 노드와 graph 상으로 연결된 Node만 돌지만 위의 코드에서는 갈 수 있는 Node를 queue에 넣어놓고 가지고 다닌다는 것이다. 또한, 방문한 Node를 또 방문하는 경우는 없는 tree구조이기 때문에 방문을 확인하는 변수 또한 두지 않았다. 재귀함수의 종료 조건은 늑대의 수가 양의 수보다 많아지는 경우이다. 종료되는 경우는, 해당 Node를 방문하면 안된다는 것이 아니라, 다른 순서로 방문(다른 곳을 먼저 방문하여 양을 더 모운 뒤 방문)해야한다는 뜻이다.