프로그래머스 - 양과 늑대 Cpp

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

• 프로그래머스 - 양과 늑대 Cpp

문제 풀이

이 문제의 가장 어려운 점은 한번 방문한 노드를 여러번 방문할 수 있다는 것이다. 중복을 허용한 탐색을 진행하면 탐색이 끝나지 않으므로, 최대한 중복 방문을 제거하기 위해 비트마스크 를 이용해 방문한 노드들을 관리하면서 같은 상태에서 같은 노드 방문을 못하게 하는게 이 문제의 핵심이다.
그 다음으로 어려웠던 부분은 이 탐색의 끝은 항상 루트 노드에서 끝나야 한다는 점이고, 반대로 생각하면 루트 노드에서 탐색 가능한 범위만 정답이 될 수 있는 것이다. 처음에 이 부분을 염두하지 않아서 계속 틀렸다. 이 두 부분만 잘 염두 하면 이 문제를 해결하는데 큰 어려움은 없다.

전체 소스 코드

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int maxValue = 0;

void dfs(int sheep, int woof, int start, int state, vector<int> info, vector<vector<int>>& grape, vector<vector<bool>>& check) {
    if (woof >= sheep) {
        return;
    }

    maxValue = max(maxValue, sheep);

    for (int i = 0; i < info.size(); i++) {
        int node = 1 << i;
        int isVisited = state & node;
        int nextState = state | node;

        if (grape[start][i] == 0) {
            continue;
        }

        if (check[nextState][i] == true) {
            continue;
        }

        check[nextState][i] = true;
        if (isVisited) {
            dfs(sheep, woof, i, nextState, info, grape, check);
        } else {
            if (info[i] == 0) {
                dfs(sheep + 1, woof, i, nextState, info, grape, check);
            } else {
                dfs(sheep, woof + 1, i, nextState, info, grape, check);
            }
        }
        check[nextState][i] = false;
    }
}

int solution(vector<int> info, vector<vector<int>> edges) {
    int answer = 0;
    vector<vector<int>> grape = vector<vector<int>>(info.size() + 1, vector<int>(info.size() + 1, 0));
    vector<vector<bool>> check = vector<vector<bool>>((1 << 18) - 1, vector<bool>(17 + 1, false));

    for (vector<int> edge : edges) {
        int from, to;
        from = edge[0];
        to = edge[1];

        grape[from][to] = 1;
        grape[to][from] = 1;
    }

    maxValue = 0;
    int state = 1 << 0;
    check[state][0] = true;

    dfs(1, 0, 0, state, info, grape, check);

    answer = max(maxValue, answer);

    return answer;
}