[틀림] 프로그래머스 양과늑대 c++ // 상태기반 dfs 방법 , 비트마스킹

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

프로그래머스

1. 상태기반 dfs 방법

필요데이터 : 왼쪽자식번호, 우측자식번호, 

vis[0000001111] 상태에 추가된 비트정보

ex) 000001 (상태1) (0번노드 있는상태)

      000011(상태3) (0번노드, 1번노드 있는상태)

      001011(상태8+2+1) (0번노드,1번노드,3번노드 있는 상태)

 

* 다음상태로 넘어가기

//다음상태로 넘어가기
for(int i=0;i<n;++i){
    //i번째 비트가 꺼져있는경우 넘어감
    if(!(state & (1<<i))) continue;
    if(l[i]!=-1) 
        solve(state | (1<<l[i])); //자식이있으면 그 자식비트를 키고(상태에추가) 탐색
    if(r[i]!=-1)
        solve(state | (1<<r[i]));

 

2. 전체코드

#include <bits/stdc++.h>

using namespace std;
//왼쪽자식, 오른쪽자식, 양/늑대 값
int l[20],r[20],val[20]; 
int n; //info 크기
int ans=1;
int vis[1<<17]; // vis[x]:상태 x를 방문했는가?

//상태에 대해 dfs
void solve(int state){
    if(vis[state]) return;
    vis[state]=1;
    
    int wolf=0, num=0; //늑대의수, 전체정점의 수 조사
    for(int i=0;i<n;++i){ //현재상태에 켜져있는 노드에 대해
        if(state & (1<<i)){
            num++;
            wolf+=val[i];
        }
    }
    if(wolf*2>=num) return; //늑대가 절반이상이면 종료
    ans=max(ans,num-wolf); //현재 state의 양의수 갱신
    
    //다음상태로 넘어가기
    for(int i=0;i<n;++i){
        //i번째 비트가 꺼져있는경우 넘어감
        if(!(state & (1<<i))) continue;
        if(l[i]!=-1) 
            solve(state | (1<<l[i])); //자식이있으면 그 자식비트를 키고(상태에추가) 탐색
        if(r[i]!=-1)
            solve(state | (1<<r[i]));
    }
}
int solution(vector<int> info, vector<vector<int>> edges) {
    n=info.size();
    fill(l,l+n,-1);
    fill(r,r+n,-1);
    for(int i=0;i<n;++i) val[i]=info[i];
    for(int i=0;i<n-1;++i){
        int a=edges[i][0]; //부모
        int b=edges[i][1]; //자식
        if(l[a]==-1) l[a]=b; //부모의 왼쪽자식이 없으면, 왼쪽부터 채움
        else r[a]=b;
    }
    solve(1); // 1번 상태로 시작 (0000000001) : 루트노드만 추가된상태
    return ans;
}

 

 

* 25. 8. 9. bfs java 풀이

최적해는? dfsX bfsO

Info에 각각의 상태 저장(번호, 양, 늑대, vis)

매번 양의갯수체크

vis에 자식노드들넣기 // [1,8]

vis가 다음 방문대상의 역할!!

이때, 자기자신 remove => 재방문 방지! // [ 1제거, 8 ]

import java.util.*;

class Solution {
    static ArrayList<Integer>[] adj = new ArrayList[20];
    static int[] arr = new int[4];
    static int ret;
    
    static class Info{
        int sheep, wolf, node;
        HashSet<Integer> vis;
        
        Info(int node, int sheep, int wolf, HashSet<Integer> vis){
            this.node=node;
            this.sheep=sheep;
            this.wolf=wolf;
            this.vis=vis;
        }
    }
    
    public int solution(int[] info, int[][] edges) {
        int answer = 0;
        int n = info.length;
        for(int i=0;i<n;++i){
            adj[i]=new ArrayList<>();
        }
        for(var edge : edges){
            var a = edge[0];
            var b = edge[1];
            adj[a].add(b);
            // adj[b].add(a);
        }
        
        ArrayDeque<Info> q = new ArrayDeque<>();
        q.offer(new Info(0,1,0,new HashSet<>()));
        
        while(q.size()>0){
            var now = q.poll();
            ret = Math.max(ret, now.sheep);
            now.vis.addAll(adj[now.node]); // 자식들 방문 기록!!!
            
            for(var nxt : now.vis){ // adj(X), now.vis(O) !!!
                var set = new HashSet<>(now.vis);
                
                set.remove(nxt); //자기자신 제거 => 재방문 막기
                
                if(info[nxt] == 1){ //늑대
                    if(now.sheep != now.wolf+1 ) //가능한 경우에만 가기
                        q.offer(new Info(nxt, now.sheep, now.wolf+1, set));
                }
                else{ //양이면 무조건 가셈
                    q.offer(new Info(nxt, now.sheep+1, now.wolf, set));
                }
            }
        }
        
        return ret;
    }
}