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

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

최초 코드

import java.util.*;

class Solution {
    private int[][] adj;
    private int maxLambs;
    
    public int solution(int[] info, int[][] edges) {
        adj = new int[info.length][info.length];
        //1. adj생성 (1:양, 2:늑대)
        for(int[] edge : edges){
            int n1 = edge[0];
            int n2 = edge[1];
            adj[n1][n2]=info[n2]+1;
            adj[n2][n1]=info[n1]+1;
        }
        bfs();
        
        return maxLambs;
    }
    
    private void bfs(){
        Queue<List<int[]>> q = new LinkedList<>();
        List<int[]> first = new ArrayList<>(4);
        
        first.add(new int[]{0});
        first.add(new int[]{1,0});
        
        first.add(new int[2*adj.length+1]);
        first.get(2)[0]=1;
        
        first.add(new int[]{1});
        first.add(new int[]{0});
        
        q.offer(first);
        
        while(!q.isEmpty()){
            List<int[]> polled = q.poll();
            int currentNode = polled.get(0)[0];
            int[] animalCnt = polled.get(1);
            int lambCnt = animalCnt[0];
            int wolfCnt = animalCnt[1];
            int[] history = polled.get(2);
            int nodeCnt = polled.get(3)[0];
            
            //모든 서브트리를 다 탐색했을 때 양의 최댓값 갱신
            if(nodeCnt>=2*adj.length){
                maxLambs = Math.max(maxLambs, animalCnt[0]);
                continue;
            }
            int tempCnt=0;
            
            for(int i=0; i<adj.length; i++){
                if(adj[currentNode][i]!=0){
                    List<int[]> e = new ArrayList<>();
                    e.add(new int[]{i});
                    //지나온 노드인 경우
                    final int _i = i;
                    if(history[i]!=0){
                        e.add(new int[]{lambCnt, wolfCnt});
                        e.add(history);
                    }
                    //처음 방문한 노드인 경우
                    else{
                        //다음 방문할 노드가 늑대일 때, 양과 늑대+1 비교
                        if(adj[currentNode][i]==2){
                            if(wolfCnt+1 >= lambCnt){
                                continue;
                            }
                            e.add(new int[]{lambCnt, wolfCnt+1});
                        }
                        else{
                            e.add(new int[]{lambCnt+1, wolfCnt});
                        }
                        int[] newHistory = Arrays.copyOf(history, history.length);
                        newHistory[i]=1;
                        e.add(newHistory);
                    }
                    e.add(new int[]{nodeCnt+(++tempCnt)});
                    q.offer(e);
                }
            }
            
        }
    }
}

 

해맨 부분

큐의 요소는 양, 늑대의 마릿수, 지나온 노드 경로, 방문한 노드 cnt 총 4가지 정보가 들어가도록 했는데 자바에서 이를 구현하려다 보니 자료구조가 너무 복잡해졌다. 

*Arrays.copyOf()정리

 

 

시나리오를 쓰고 시현을 돌리며 확신을 얻기까지 한시간, 구현하는 데 한시간 반 정도 걸려서 푼 것 같다..

그런데도 위와 같은 결과를 받게 됐다. 내일 이어서 하고 베스트 풀이도 같이 정리해보도록 하자.

 

 

개선 코드 (인접행렬 -> 인접리스트, 늑대가 있는 리프노드 enqueueX)

import java.util.*;

class Solution {
    private List<List<Integer>> adj;
    private List<List<Integer>> lambOrWolf;
    
    private int maxLambs;
    
    public int solution(int[] info, int[][] edges) {
        adj = new ArrayList<>(info.length);
        lambOrWolf = new ArrayList<>();
        
        for(int i=0; i<info.length; i++){
            adj.add(new ArrayList<>());
            lambOrWolf.add(new ArrayList<>());
        }
        //1. adj생성 (1:양, 2:늑대)
        for(int[] edge : edges){
            int n1 = edge[0];
            int n2 = edge[1];
            adj.get(n1).add(n2);
            adj.get(n2).add(n1);
            
            lambOrWolf.get(n1).add(info[n2]+1);
            lambOrWolf.get(n2).add(info[n1]+1);
        }
        bfs();
        
        return maxLambs;
    }
    
    private void bfs(){
        Queue<List<int[]>> q = new LinkedList<>();
        List<int[]> first = new ArrayList<>(4);
        
        first.add(new int[]{0});
        first.add(new int[]{1,0});
        
        first.add(new int[2*adj.size()+1]);
        first.get(2)[0]=1;
        
        first.add(new int[]{1});
        first.add(new int[]{0});
        
        q.offer(first);
        
        while(!q.isEmpty()){
            List<int[]> polled = q.poll();
            int currentNode = polled.get(0)[0];
            int[] animalCnt = polled.get(1);
            int lambCnt = animalCnt[0];
            int wolfCnt = animalCnt[1];
            int[] history = polled.get(2);
            int nodeCnt = polled.get(3)[0];

            //모든 서브트리를 다 탐색했을 때 양의 최댓값 갱신
            if(nodeCnt>=2*adj.size()){
                maxLambs = Math.max(maxLambs, animalCnt[0]);
                continue;
            }
            int tempCnt=0;
            
            for(int i=0; i<adj.get(currentNode).size(); i++){
                int nextNode = adj.get(currentNode).get(i);
                
                //다음 노드가 리프노드이면서 늑대일 때 Queue추가 x
                if(adj.get(nextNode).size()<2 && lambOrWolf.get(currentNode).get(i)==2){
                    continue;
                }
                    List<int[]> e = new ArrayList<>();
                    e.add(new int[]{nextNode});
                    //지나온 노드인 경우
                    if(history[nextNode]!=0){
                        e.add(new int[]{lambCnt, wolfCnt});
                        e.add(history);
                    }
                    //처음 방문한 노드인 경우
                    else{
                        //다음 방문할 노드가 늑대일 때, 양과 늑대+1 비교
                        if(lambOrWolf.get(currentNode).get(i)==2){
                            if(wolfCnt+1 >= lambCnt){
                                continue;
                            }
                            e.add(new int[]{lambCnt, wolfCnt+1});
                        }
                        else{
                            e.add(new int[]{lambCnt+1, wolfCnt});
                        }
                        int[] newHistory = Arrays.copyOf(history, history.length);
                        newHistory[nextNode]=1;
                        e.add(newHistory);
                    }
                    e.add(new int[]{nodeCnt+(++tempCnt)});
                    q.offer(e);
            }
        }
    }
}

 

모법 답안

class Solution {
    private boolean[] visited;
    private int maxSheeps = 1; 
    
    public int solution(int[] info, int[][] edges) {
        visited = new boolean[info.length];
        visited[0]=true;
        
        dfs(1,0, info, edges);
        
        return maxSheeps;
    }
    
    private void dfs(int sheep, int wolf, int[] info, int[][] edges){
        if(sheep<=wolf){
            return;
        }
        
        maxSheeps = Math.max(maxSheeps, sheep);
        
        // 주어진 간선을 인접리스트로 만들지 않고 바로 순회
        for(int[] edge : edges){
            int parent = edge[0];
            int child = edge[1];
            
            //부모노드는 방문, 자식노드는 방문하기 전일 때 탐색
            //즉 어떤 노드를 접근할 때 자식노드로 먼저 접근해야 그 노드가 부모노드로 등장할 때 해당 edge를 탐색할 수 있음
            if(visited[parent] && !visited[child]){
                //백트래킹
                visited[child]=true;
                if(info[child]==0){
                    dfs(sheep+1, wolf, info, edges);
                } else{
                    dfs(sheep, wolf+1, info, edges);
                }
                visited[child]=false;
            }
        }
    }
}

 

시나리오

1. 매 뎁스마다 양과 늑대의 수를 비교하고 양<=늑대일 때는 return, 양>늑대일 때는 최댓값을 갱신한다.

2. 입력으로 주어진 edges를 순회한다. 이 때 부모노드는 이미 방문했으며, 자식노드는 아직 방문하지 않을 때 자식노드를 탐색한다. 

3. 자식노드가 양인 경우 양+1, 늑대를 매개변수로하는 재귀호출, 늑대인 경우는 반대로 호출한다.

4. maxSheep 리턴

 

2.의 방법으로 dfs를 구현하면 매 호출마다 edges를 순회하기 때문에 기본적으로 깊이 우선탐색으로 동작하되 루트노드로 돌아가 다른 서브트리를 탐색하는 경우의 수도 구할 수 있다.

 

출처: https://velog.io/@thguss/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-L3-%EC%96%91%EA%B3%BC-%EB%8A%91%EB%8C%80-python