[알고리즘] 2022 KAKAO BLIND 양과 늑대 (Java)

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

프로그래머스

 

2진 트리 형태로 되어있고, 양의 수 > 늑대의 수를 유지하며 최대한 많은 양을 확보해야하는 문제이다.

 

처음에는 우선 순위 큐와 유니온 파인드를 활용하여 풀어볼라 했지만, 아이디어를 얻기 힘들어 다른 방식을 생각했다.

 

기본적으로 DFS 방식으로 시작 위치인 0번째 노드부터 탐색을 시작하며 양인지 늑대인지 확인 후

 

양인 경우 최대로 모인 양의 수와 비교하며 갱신하고, 늑대의 수가 양의 수와 같아지는 경우 DFS 탐색을 종료하는 방식으로 구현했다.

 

각 DFS 마다 edges 배열을 전부 확인하며 아직 방문하지 않은 노드로 연결된 간선이 있는 경우 해당 위치로 이동하여

 

DFS를 진행하는 방식으로 진행했다.

 

 

import java.io.*;
import java.util.*;
import java.math.*;

class Solution {
    static int answer,N;
    
    public void dfs(int idx, boolean isVisited[], int info[], int edges[][], int lamb, int wolf){
        isVisited[idx] = true;
        
        if(info[idx]==0){
            lamb++;
            answer = Math.max(answer,lamb);
        }
        else{
            wolf++;
        }
        
        if(lamb<=wolf){
            return;
        }
        
        for(int next[] : edges){
            if(isVisited[next[0]] && !isVisited[next[1]]){
                
                dfs(next[1], isVisited, info, edges, lamb, wolf);
                isVisited[next[1]] = false;
            }
        }
    }
    
    public int solution(int[] info, int[][] edges) {
        
        N = info.length;
        boolean isVisited[] = new boolean[N];
        
        answer = 0;
        dfs(0,isVisited,info,edges,0,0);
        
        return answer;
    }
}