[DFS 순열, 그래프, 비트] 프로그래머스 양과 늑대 C++

 

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

프로그래머스

#include <string>
#include <vector>

using namespace std;

vector<int> v[17];
vector<int> animal(17);
bool visited[17];
int answer;

void dfs(int idx, int lamb, int wolf, int path) {
    if (animal[idx] == 0) lamb++;
    else wolf++;
    
    if (lamb <= wolf) lamb = 0;
    answer = max(answer, lamb);
    
    for(auto vec : v[idx]) path |= (1<<vec); // 갈 수 있는 경로

    for(int i=0; i<animal.size(); i++) {
        if (visited[i]) continue;
        if ((path & (1<<i)) != (1<<i)) continue;
        visited[i] = true;
        dfs(i, lamb, wolf, path);
        visited[i] = false; // DFS 순열
    }
}

int solution(vector<int> info, vector<vector<int>> edges) {
    for(int i=0; i<info.size(); i++) animal[i] = info[i];
    for(auto e : edges) {
        v[e[0]].push_back(e[1]);
        v[e[1]].push_back(e[0]);
    }
    
    visited[0] = true;
    dfs(0, 0, 0, 0);
    
    return answer;
}

경로 표시