[Programmers] 양과 늑대 (카카오 2022 공채)

[문제 링크]

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

프로그래머스

 

 

[코드]

import java.util.*;

class Solution {
    class Node {
        int value; // 0:양, 1:늑대
        Node left;
        Node right;
        
        public Node (int value) {
            this.value = value;
        }
    }
    
    int maxSheep = 0;
    
    public int solution(int[] info, int[][] edges) {
        
        Node[] nodes = new Node[info.length];
        
        // 노드 생성
        for(int i = 0; i < info.length; i++) {
            nodes[i] = new Node(info[i]); // 0:양, 1:늑대
        }
        
        // child 설정
        for(int[] edge : edges) {
            int root = edge[0];
            
            if(nodes[root].left == null) {
                nodes[root].left = nodes[edge[1]];
            } else {
                nodes[root].right = nodes[edge[1]];
            }
        }
        
        List<Node> canVisit = new ArrayList<>();
        canVisit.add(nodes[0]);
        
        dfs(nodes[0], 0, 0, canVisit);
        
        
        return maxSheep;
    }
    
    public void dfs (Node current, int sheep, int wolf, List<Node> canVisit) {
        if(current.value == 0) {
            sheep++;
        } else {
            wolf++;
        }
        
        // 양보다 늑대가 많으면 끝
        if(wolf >= sheep) {
            return;
        }
        
        maxSheep = Math.max(maxSheep, sheep);
        
        List<Node> newCanVisit = new ArrayList<>(canVisit);
        
        // 새로운 노드 배열에서 현재 방문한 current 노드 삭제
        newCanVisit.remove(current);
        
        if(current.left != null) {
            newCanVisit.add(current.left);
        }
        
        if(current.right != null) {
            newCanVisit.add(current.right);
        }
        
        for(Node n : newCanVisit) {
            dfs(n, sheep, wolf, newCanVisit);
        }
    }
}

[회고]

처음에 풀지를 못해서 풀이과정을 보고 풀어봤습니다.항상 어려운 문제들은 풀이과정을 보고 이해하고 구현하게 되네요.그래도 이해하고 스스로 구현할 수 있게 된 게 어딥니까!

스스로 풀 수있을때까지 가봐야죠 ~
파이팅

 

 

 

 

질문과 피드백은 언제나 환영입니다.

감사합니다.