[Algorithm] 프로그래머스 - 양과 늑대 자바 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

 

이번 포스팅은 프로그래머스 양과 늑대에 대한 자바 풀이를 작성하도록 하겠습니다.

 

문제 출처: https://school.programmers.co.kr/learn/courses/30/lessons/92343

프로그래머스

 

 

1. 풀이 소스

 

import java.util.*;

class Solution {
    
    int maxSheepCnt; // 최대 양의 수
    int totalSheepCnt; // 총 양의 수
    ArrayList<Integer>[] nodes; // A 노드의 자식 노드(B, C, D)와 부모(R)를 포함한 조상 노드(X, Y)의 자식 노드 중 방문해야하는 노드들
    
    public int solution(int[] info, int[][] edges) {
        
        nodes = new ArrayList[info.length]; 
        
        for (int i = 0; i < nodes.length; i++) nodes[i] = new ArrayList<>();
        
        for (int i = 0; i < info.length; i++) {
            if (info[i] == 0) totalSheepCnt++; // 총 양의 수를 구하여, 만약 최대 양의 수가 총 양의 수와 같다면 무조건 리턴
        }
        
        if (totalSheepCnt == 0) return 0; // 만약 총 양의 수가 0 이라면 바로 종료
        
        for (int[] edge : edges) {
            int parent = edge[0]; 
            int child = edge[1];
            nodes[parent].add(child); // 단방향 간선을 설정 (부모 -> 자식으로만 이동)
        }
     
        dfs(0, 0, 0, new ArrayList<>(), info);
        
        return maxSheepCnt;
    }
    
    void dfs(int sheepCnt, int wolfCnt, int node, List others, int[] info) {
        if (maxSheepCnt == totalSheepCnt) return; // 총 양의 수와 최대 방문한 양의 개수가 같다면 dfs 종료
        
        if (info[node] == 0) sheepCnt++;
        else wolfCnt++;
        maxSheepCnt = Math.max(maxSheepCnt, sheepCnt);
        
        if (sheepCnt <= wolfCnt) return; // 문제에서 늑대가 양의 개수보다 더 크다면 현재 dfs 종료
        
        List<Integer> remains = new ArrayList<>();
        remains.addAll(others); // 재귀로 남아 있는 리스트를 그대로 새로운 리스트에 추가
        // 예제 1 기준 루트 노드부터 선택되지 않았던 자식노드 ex)8, 현재 노드가 4번이라면 방문해야하는 노드2 추가
        
        if (!nodes[node].isEmpty()) {
            remains.addAll(nodes[node]); // 현재 노드의 자식 노드 추가
        }
        
        remains.remove(Integer.valueOf(node)); // remove에 레퍼타입을 적용하면 해당 값은 index가 아닌 value로 제거 가능
        
        for (int nextNode : remains) {
            dfs(sheepCnt, wolfCnt, nextNode, remains, info);
        }
    }
}

 

 

2. 주의할 점

 

 

• 일반적인 dfs를 적용하게 된다면 다음과 같이 자식 노드를 기준으로 탐색하게 됩니다. 하지만, 늑대의 개수가 양보다 큰 경우 8번을 먼저 방문할 수 없습니다. 즉, 루트 노드(0)의 자식 노드 8번을 거치지 않게 됩니다. 따라서, 이 문제를 극복하기 위해 특정 A 노드로 방문하고자 할 때, 부모노드와 조상 노드에서 방문하지 않은 노드를  아래의 사진처럼 추가하여 재방문할 수 있도록 해야 합니다.

 

• 문제 되는 부분은 방문하지 않은 노드를 선택할 때, 부모 노드의 자식 노드를 전부 추가하게 되면 양 2가 중복되게 됩니다. 
• 자바의 list.remove()를 활용할 때 레퍼 변수 Integer 변수를 사용하게 되면 인덱스가 아닌 값을 제거할 수 있습니다.

 

나머지는 주석으로 처리하였습니다! 이상으로 해당 문제 리뷰를 마치겠습니다.

 

감사합니다.!!!