프로그래머스 <양과 늑대>

프로그래머스 <양과 늑대>

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

프로그래머스

---

양과 늑대

2진 트리 모양 초원의 각 노드에 늑대와 양이 한 마리씩 놓여 있습니다. 이 초원의 루트 노드에서 출발하여 각 노드를 돌아다니며 양을 모으려 합니다. 각 노드를 방문할 때 마다 해당 노드에 있던 양과 늑대가 당신을 따라오게 됩니다. 이때, 늑대는 양을 잡아먹을 기회를 노리고 있으며, 당신이 모은 양의 수보다 늑대의 수가 같거나 더 많아지면 바로 모든 양을 잡아먹어 버립니다. 당신은 중간에 양이 늑대에게 잡아먹히지 않도록 하면서 최대한 많은 수의 양을 모아서 다시 루트 노드로 돌아오려 합니다.
모을 수 있는 양의 최대 수를 구하세요.

---

문제해결

어떻게 풀어야 되나 고민을 했는데 노드의 개수가 최대 17개이길래 재귀함수로 풀 수 있을 것 같았다.

 

시작 노드는 0으로 고정되어 있다. 방문 체크를 할 때, 양의 수와 늑대의 수를 가지고 방문 체크를 진행했다.

recursion(int node, int sheep, int wolf, int[][] visit, int[] info)

• node : 현재 노드의 번호
• sheep : 현재까지 모은 양의 수
• wolf : 현재까지 모은 늑대의 수
• visit[i] : i번 노드에 왔을 때, {양의 수, 늑대의 수}
• info[i] : i번 노드에 있는 동물의 종류(0이면 양, 1이면 늑대)

로직

• 현재 노드(=node)를 방문 체크를 진행하고 answer 값을 업데이트 한다.
• 현재 노드의 인접 노드(=near)를 본다.
  • 인접 노드가 양이고 방문한 적이 없다면 재귀 함수를 호출한다.
    recursion(near, sheep+1, wolf, deepcopy(visit), info)
  • 인접 노드가 늑대이고 방문한 적이 없고 양의 수(sheep)가 현재 늑대의 수(wolf + )1보다 크다면 재귀 함수를 호출한다. 
    recursion(near, sheep, wolf+1, deepcopy(visit), info)
  • 위의 두가지 경우가 모두 아니라면 방문하지 않았을 때만 재귀 함수를 호출한다.
    recursion(near, sheep, wolf, deepcopy(visit), info)

---

코드

import java.util.*;
class Solution {
    static int answer;
    static ArrayList<ArrayList<Integer>> adj; 

    public int solution(int[] info, int[][] edges) {
        adj = new ArrayList<>();
        for(int i = 0; i < info.length; i++){
            adj.add(new ArrayList<>());
        }
        for(int i = 0; i < edges.length; i++){
            int a = edges[i][0];
            int b = edges[i][1];
            adj.get(a).add(b);
            adj.get(b).add(a);
        }
        
        answer = 0;
        int[][] visit = new int[info.length][2];
        recursion(0, 1, 0, visit, info);
        return answer;
    }
    static void recursion(int node, int sheep, int wolf, int[][] visit, int[] info){
        // 방문 체크
        visit[node][0] = sheep;
        visit[node][1] = wolf;
        answer = Math.max(answer, sheep);
        for(int i = 0; i < adj.get(node).size(); i++){
            int near = adj.get(node).get(i);
            if(info[near] == 0 && (visit[near][0] == 0 && visit[near][1] == 0)) {   // 양인 경우
                recursion(near, sheep+1, wolf, deepcopy(visit), info);
            }else if(info[near] == 1 && (visit[near][0] == 0 && visit[near][1] == 0)){  // 늑대인 경우
                if(sheep > wolf + 1){
                    recursion(near, sheep, wolf+1, deepcopy(visit), info);
                }
            }else{
                // 방문 체크
                if(visit[near][0] == sheep && visit[near][1] == wolf) continue;
                recursion(near, sheep, wolf, deepcopy(visit), info);
            }
        }
        
    }
    
    static int[][] deepcopy(int[][] arr){
        int[][] copy = new int[arr.length][arr[0].length];
        for(int i = 0; i < arr.length; i++){
            for(int j = 0; j < arr[0].length; j++){
                copy[i][j] = arr[i][j];
            }
        }
        return copy;
    }
}

---

결과

---