[프로그래머스] 2022 카카오 블라인드 양과 늑대 - JAVA

문제

양과 늑대
각 노드에 있는 양 또는 늑대에 대한 정보가 담긴 배열 info, 2진 트리의 각 노드들의 연결 관계를 담은 2차원 배열 edges가 매개변수로 주어질 때, 문제에 제시된 조건에 따라 각 노드를 방문하면서 모을 수 있는 양은 최대 몇 마리인지 return 하도록 solution 함수를 완성해주세요.

풀이

dfs와 비트마스킹을 통해 풀었습니다.
먼저 visited라는 boolean타입의 배열을 만들어줍니다. visited의 역할은 다음과 같습니다.
만약 5개의 노드중 1번노드와 2번노드를 방문했다고 합시다 이를 비트로 나타내주면 다음과 같이 표현할 수 있습니다.
00011
이를 다시 10진수로 계산해보면 2+1 = 3이됩니다. 이 3에 해당하는 index를 visited배열에서 true로 설정해 놓는겁니다.
이를 통해 상태가 같은 경우 즉 방문한 노드들이 같은 경우 return처리를 해주어 중복을 방지하여 시간복잡도를 줄였습니다.

예를들어 00001의 상태에서 00011로 상태가 변경됐다고 해봅시다. 해당 상태를 visited배열로 확인후 false라면 비트마스킹을 통해 어느 비트가 켜져있는지 확인해 줍니다.
여기서는 1번과 2번이 켜져있는걸 알 수 있습니다.
비트가 켜져있는 곳의 갯수와 늑대의 마리수를 구해줍니다.
만약 전체 갯수 <= 2*늑대의 마리수 라면 return해줍니다.
이는 다시 말하면 늑대가 전체에서 절반 이상이라는 말이니 방문할 수 없는 상태이기 떄문에 return을 해주는 겁니다.

전체 갯수 > 2*늑대의 마리수 라면 answer을 현재 양의 마리수와 answer중 최댓값으로 갱신해줍니다.

다시 켜져있는 비트들을 찾고 해당 비트에 해당하는 자식 노드들을 방문해 줍니다. 이때 자식 노드의 비트를 켜야하므로 or 연산을 통해 해당 비트를 1로 만들어 줘야 합니다.

코드

import java.util.*;

class Solution {
    public int[] Info;
    public int answer = 0;
    public boolean[] visited;
    public ArrayList<ArrayList<Integer>> nodes = new ArrayList<>();
    public void dfs(int state) {
        if(visited[state]) return;
        visited[state] = true;
        int sum = 0;
        int wolf = 0; 
        for(int i=0; i<Info.length; i++) {
            if((state & (1 << i)) != 0) {
                sum++;
                wolf+=Info[i];
            }
        }
        
        if(2*wolf>=sum) return;
        answer = Math.max(answer,sum-wolf);
        
        for(int i=0; i<Info.length; i++) {
            if((state & (1 << i)) != 0) {
                for(int next: nodes.get(i)) {
                    dfs(state | (1 << next));
                }
            }
        }
    }
    public int solution(int[] info, int[][] edges) {
        Info = info;
        visited = new boolean[1<<info.length];
        for(int i=0; i<info.length; i++) {
            nodes.add(new ArrayList<>());
        }
        
        for(int i=0; i<edges.length; i++) {
            nodes.get(edges[i][0]).add(edges[i][1]);
        }
        dfs(1);
        return answer;
    }
    
}