프로그래머스 - 양과 늑대 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;}