[프로그래머스 92343] 양과 늑대

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

프로그래머스

완전 탐색이 하기 싫어서..  우선 순위 큐를 적용하여 풀이하는 방법으로 계속 생각해 보았지만 예외 케이스가 내 눈에도 계속 보였다ㅜ 

결국 완전 탐색으로 ㄱㄱ

 

 

👇 참고 문서 

https://school.programmers.co.kr/questions/25736 

프로그래머스

 

 

이 문제는 무한 루프에 빠지지 않게, 즉 탐색했던 정점을 또 탐색하게 되는 일이 없도록 하는 게 제일 중요한 것 같다

- isVisited 3차원 배열으로 중복 제거 {현재 sheep, wolf, idx}

- LinkedList<Integer> nextList 를 인자로 전달

nextList(현재 이동 가능한 노드 리스트)를 인자로 전달할 때 새로 생성해서 전달해야 한다

-> 독립적으로 사용되어야 하기 때문 !!

 

중복을 제거하기 위해 위의 두 방식을 적용하였는데, 대부분 둘 중 하나의 방법으로 풀이한 듯 하다... ㅎ

3차원 배열 & nextList 사용하였을 때가 nextList만 사용하였을 때보다 3~5배 더 빨랐음(어찌되었든 둘 다 무난하게 통과)

 

 

사실상 늑대의 수 때문에 dfs에 가지치기가 적용되었다고 할 수 있지만, 불안해서. ... ...

 

import java.util.ArrayList;
import java.util.LinkedList;

class Solution {
   boolean[][][] isVisited;
   ArrayList<Integer>[] childList;

   int maxSheep = 0;
   public int solution(int[] info, int[][] edges) {
      //init
      int cnt = info.length;
      isVisited = new boolean[cnt + 1][cnt + 1][cnt];        //{현재 sheep 수, wolf 수, idx}
      childList = new ArrayList[cnt];
      for (int i = 0; i < cnt; i++) {
         childList[i] = new ArrayList<>();
      }
      for (int i = 0; i < edges.length; i++) {
         childList[edges[i][0]].add(edges[i][1]);
      }
      LinkedList<Integer> vertexList = new LinkedList<>();
      vertexList.add(0);
      dfs(info, vertexList, 0, 1, 0);
      return maxSheep;
   }

   private void dfs(int[] info, LinkedList<Integer> vertexList, int curr, int currSheep, int currWolf) {
      if (isVisited[currSheep][currWolf][curr]) {
         return;
      }

      maxSheep = Math.max(currSheep, maxSheep);
      isVisited[currSheep][currWolf][curr] = true;

      vertexList.addAll(childList[curr]);
      vertexList.remove(Integer.valueOf(curr));
      for (Integer next : vertexList) {

         if (info[next] == 0) {    //sheep
            dfs(info, new LinkedList<>(vertexList), next, currSheep + 1, currWolf);
         } else {                //wolf
            if (currSheep > currWolf + 1) {
               LinkedList<Integer> nextList = new LinkedList<>(vertexList);
               dfs(info, nextList, next, currSheep, currWolf + 1);
            }
         }
      }
   }
}