2022 카카오 블라인드 코딩테스트 5번

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

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

2022 카카오 블라인드채용 1차 코딩테스트의 5번 문제

비트마스킹과 dfs를 이용했음

#include <string>
#include <vector>
#define MAX 17
using namespace std;
vector<int> tree[MAX];
vector<int> worfState;
int state[1 << MAX];
int sol = 1;

int max(int a, int b) { return a > b ? a : b; }

//현재 방문한 노드의 상태를 S로 나타냄
void dfs(int s) {

	//현재 노드 상태는 계산 여부 확인
	if (state[s]) return;
	state[s] = 1;

	int num = 0, worfCnt = 0;
	for (int i = 0; i < worfState.size(); i++) {
		//방문한 노드의 카운팅과 늑대 수 관리
		if (s&(1 << i)) {
			num++;
			worfCnt += worfState[i];
		}
	}

	//총 방문한 노드의 수가 현재 늑대의 수 x 2를 했을때 같거나 작으면 불가능한 케이스
	if (worfCnt * 2 >= num) return;

	sol = max(sol, num - worfCnt);

	//다음 노드 탐색
	for (int i = 0; i < worfState.size(); i++) {
		//방문하지 않은 노드에서 해당 노드의 자식노드로 가는 것은 불가능함
		if (!(s&(1 << i))) continue;

		//방문했던 노드중 자식 노드가 있다면 state변경하여 해당 케이스 탐색
		for (auto iter : tree[i]) {
			dfs(s | (1 << iter));
		}
	}
}
//비트 마스킹 사용예정 / 방문한 노드를 1, 방문하지 않은 노드 0처리
int solution(vector<int> info, vector<vector<int>> edges) {
	//늑대정보를 전역화
	for (auto iter : info)
		worfState.push_back(iter);

	int num = 0;
	//트리정보 전역화
	for (auto iter : edges)
		tree[iter[0]].push_back(iter[1]);

	//0번째 노드를 방문한 상태는 비트로 00...01임
	dfs(1);

	int answer = sol;
	return answer;
}

int solution(vector<int> info, vector<vector<int>> edges) {

	for (auto iter : info)
		worfState.push_back(iter);

	for (auto iter : edges)
		tree[iter[0]].push_back(iter[1]);

	dfs(1);

	int answer = sol;
	return answer;
}

아이디어

비트마스킹을 공부하고 있는 상태라 그런지 보자마자 비트마스킹이라고 생각했음

그런데 트리구조이기 때문에 반드시 부모노드로 부터 자식 노드로 이동 해야하는 문제가 있었음을 인지했음에도 본인의 생각대로 구현시작

1일때 방문 0일때 방문하지 않음으로 처리하여 첫 시도에는 일반적인 비트마스킹 구조로 모든 케이스를 for문으로 탐색했고 1처리된 부분의 노드를 확인할때 해당 노드의의 부모도 1인지 확인하는 바텀업 방식으로 구현했는데 점점 복잡해져갔음 이때 다른 방법으로 풀이를 해야한다는 느낌이 들었음

반드시 부모로부터 탐색을 시작하는 탑다운 방식이 필요 하다 생각했고 바킹독님의 풀이를 참고하게 됨

코드의 핵심은 29번라인인 다음 노드 탐색 여부 조건을 파악하는 것이라고 느껴짐