프로그래머스 Level 3 양과늑대

양과늑대 (프로그래머스 Level 3)

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

처음에는 BFS로 탐색하면 될 것 같았으나,
문제가 하나 있었다

‘이전’에 ‘조건(양 <= 늑대)’에 만족하지 않았으나
다른 위치에서 조건을 만족한 경우, ‘재탐색’을 어떻게 해야할 지가
가장 큰 문제였다

결국 아이디어를 찾아 여러 부분을 검색해보았다

특정 부분의 ‘더 깊은 곳’에서 ‘양’을 데려올 수 있다는 점에서,
DFS를 생각할 수 있었고,
‘이전’에 방문했는지의 여부를 체크하는 방식을 통해
‘백트래킹’을 적용할 수 있었다

가장 헷갈리던 문제인 ‘재탐색’ 부분 역시
‘방문’체크를 해제하며, 동시에
‘탐색’할 위치로 계속 지정해주는 방식을 통하여
우측 하단 노드에서 ‘좌측’의 탐색하지 못한 부분을 체크할 수 있었다

여담으로, 그래프는 정말 어려운 문제인 것 같다
조금 익숙해졌나 하였는데,
응용을 하기 정말 까다로운 것을 다시 느낀다

Code

#include <string>
#include <vector>

using namespace std;

void dfs(const vector<vector<int>>& tree, const vector<int>& info, vector<bool>& visited, int sheepCount, int wolfCount, vector<int> next, int& answer)
{
	// next 내부에 있는걸 돌면서?
	if (sheepCount <= wolfCount)
		return;

	answer = max(answer, sheepCount);

	int nSize = next.size();

	for (int i = 0; i < nSize; i++)
	{
		int now = next[i];

		if (visited[now] == true)
			continue;

		visited[now] = true;

		// 복사용
		vector<int> newNext = next;

		// 자기 자신인 i번째 요소를 지움
		// 우측 노드라도 탐색은 루트의 왼쪽 부터 탐색하기에
		// 무리 없이 재탐색할 수 있음
		newNext.erase(newNext.begin() + i);

		for (int child : tree[now])
		{
			if (visited[child] == false)
			{
				newNext.push_back(child);
			}
		}

		// 양인 경우
		if (info[now] == 0)
		{
			dfs(tree, info, visited, sheepCount + 1, wolfCount, newNext, answer);
		}
		else
		{
			dfs(tree, info, visited, sheepCount, wolfCount + 1, newNext, answer);
		}

		visited[now] = false;
	}
}

int solution(vector<int> info, vector<vector<int>> edges) {
	// dfs 와 백트래킹을 이용하여 풀기
	const int n = info.size();
	vector<vector<int>> tree(n, vector<int>());

	for (const auto& e : edges)
	{
		int begin = e[0];
		int to = e[1];
		tree[begin].push_back(to);
		tree[to].push_back(begin);
	}

	vector<bool> visited(n, false);
	
	// tree의 첫번째 요소부터 시작(루트)
	vector<int> next = tree[0];
	visited[0] = true;

	int answer = 0;
	dfs(tree, info, visited, 1, 0, next, answer);

	return answer;
}