2022 KAKAO BLIND 양과 늑대 (Java)

2022 KAKAO BLIND RECRUITMENT > 양과 늑대

 

문제 설명

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

 

제한사항

2 ≤ info의 길이 ≤ 17
info의 원소는 0 또는 1 입니다.
info[i]는 i번 노드에 있는 양 또는 늑대를 나타냅니다.
0은 양, 1은 늑대를 의미합니다.
info[0]의 값은 항상 0입니다. 즉, 0번 노드(루트 노드)에는 항상 양이 있습니다.
edges의 세로(행) 길이 = info의 길이 - 1
edges의 가로(열) 길이 = 2
edges의 각 행은 [부모 노드 번호, 자식 노드 번호] 형태로, 서로 연결된 두 노드를 나타냅니다.
동일한 간선에 대한 정보가 중복해서 주어지지 않습니다.
항상 하나의 이진 트리 형태로 입력이 주어지며, 잘못된 데이터가 주어지는 경우는 없습니다.
0번 노드는 항상 루트 노드입니다.

---

문제 접근

DFS을 사용하면서 양과 늑대의 수에 따른 조건이 있어 백트레킹을 이용했다.

 

문제를 풀다가 java.util.ConcurrentModificationException이 발생했는데 이는 dfs메소드를 호출하는 for문에서 반복 수행 대상인 nextNode가 변경되도록 해당 객체 자체에 상태를 넣고 뺐다.

 

잘못된 풀이

 

import java.util.*;

class Solution {
    private static int maxSheep;
    private static void dfs(ArrayList<Integer>[] adjList, int[] info, ArrayList<Integer> nextNode, int sheepCnt, int wolfCnt, int cur) {
        if(info[cur] == 0)
            sheepCnt++;
        else if(info[cur] == 1)
            wolfCnt++;

        if(sheepCnt <= wolfCnt)
            return;

        maxSheep = Math.max(sheepCnt, maxSheep);

        nextNode.remove(Integer.valueOf(cur));

        for(int next : adjList[cur]){
            nextNode.add(next);
        }
        
		// java.util.ConcurrentModificationException 발생 지점
        for(int next : nextNode) {
            dfs(adjList, info, nextNode, sheepCnt, wolfCnt, next);
        }
    }
    public int solution(int[] info, int[][] edges) {
      ArrayList<Integer>[] adjList = new ArrayList[info.length];

      for(int i =0 ; i < info.length; i ++)
          adjList[i] = new ArrayList<Integer>();

      for(int i =0 ; i < edges.length; i ++) {
          adjList[edges[i][0]].add(edges[i][1]);
      }

      ArrayList<Integer> nextNode = new ArrayList<>();
      nextNode.add(0);

      dfs(adjList, info, nextNode, 0, 0, 0);

      return maxSheep;
    }
}

 

상위 idx에서부터 내려가면서 각 idx에서 갈 수 있는 idx를 nextNode에 넣어야 하며 백트레킹되어 되돌아왔을 때 이 상태는 유지되어야 한다. 즉, nextNode를 넣기전에 값을 복사하여 복사된 값을 dfs의 인자로 넘거야한다.

---

맞은 풀이

import java.util.*;

class Solution {
    private static int maxSheep;

    // DFS 탐색
    private static void dfs(ArrayList<Integer>[] adjList, int[] info, ArrayList<Integer> nextNode, int sheepCnt, int wolfCnt, int cur) {
        if (info[cur] == 0) {
            sheepCnt++;
        } else if (info[cur] == 1) {
            wolfCnt++;
        }
 
        if (sheepCnt <= wolfCnt) {
            return;
        }
 
        maxSheep = Math.max(maxSheep, sheepCnt);

        // 값을 복사
        ArrayList<Integer> newNextNode = new ArrayList<>(nextNode);
        newNextNode.remove(Integer.valueOf(cur));  
 
        for (int next : adjList[cur]) {
            newNextNode.add(next);
        }

        // 복사된 리스트를 순회
        for (int next : newNextNode) {
            dfs(adjList, info, newNextNode, sheepCnt, wolfCnt, next);
        }
    }

    public int solution(int[] info, int[][] edges) {
        ArrayList<Integer>[] adjList = new ArrayList[info.length];

        for (int i = 0; i < info.length; i++) {
            adjList[i] = new ArrayList<>();
        }
 
        for(int i =0 ; i < edges.length; i ++) {
          adjList[edges[i][0]].add(edges[i][1]);
      }
 
        ArrayList<Integer> nextNode = new ArrayList<>();
        nextNode.add(0);
 
        maxSheep = 0;
        dfs(adjList, info, nextNode, 0, 0, 0);

        return maxSheep;
    }
}