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

문제 설명 :

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

프로그래머스

 

문제 요약:

1. 트리를 탐색하여 확보할 수 있는 가장 많은 양의 수 구하기
2. 대신, 항상 늑대의 수보다 양의 수가 더 많아야 됨

 

문제 풀이 시간 : 1시간

문제 성공 여부 : 실패

 

접근 방법(실패) :

1. 백트래킹으로 모든 경로에 대한 양의 최댓값 구하기

실패 이유 :

dfs로 탐색을 하는데, 도저히 가지치기를 하고 돌아온 부모 노드에서 이전에 못 갔던 노드로 가는 방법이 생각이 안 났다.

 

예를 들어, 위의 그림 같은 경우가 있다.

 

먼저 루트인 0부터 자식노드(1,2)로 이동을 한다.

 

1은 양의 수와 늑대의 수가 같아지므로 가지치기를 한다.

 

2로 가서 양을 확보하고, 5로 가서 또 양을 확보하고, 6->9->10 순으로 탐색을 하게 된다.

 

하지만, 문제의 조건을 만족하기 위해서는 0->2를 간 분기점에서 1을 가는 경우도 따져야 하고,

0->2->5->1을 가는 분기점 등, 가능한 모든 경우에서 이전에 가지 않았던 경로를 탐색해야 한다.

 

1시간가량 이 방법에 대해 고민을 했지만 결국 주어진 시간 내에 해결하지 못하였다.

 

접근 방법(성공)

1. 가장 핵심은 이전 노드(부모노드)에서 갈 수 없었던 노드들을 어떻게 다시 방문할까?이다.
2. 따라서 매 노드 방문 시, 그동안의 경로를 함께 보내서 탐색을 해주어야 한다!

 

글로는 잘 이해가 안 되므로 코드를 먼저 보겠다.

import java.util.*;
class Solution {
    static int ans; // 최대로 모을 수 있는 양의 수
    static List<Integer>[] arr; // 트리 정보
    
    public int solution(int[] info, int[][] edges) {
        int N = info.length;
        arr = new ArrayList[N];
        for(int i = 0; i<N; i++) arr[i] = new ArrayList<>();
        
        for(int i = 0; i<edges.length; i++){ // 트리 정보 갱신
            int from = edges[i][0];
            int to = edges[i][1];
            
            arr[from].add(to);
        }
        
        ans = 0;
        
        List<Integer> route = new ArrayList<>(); // 현재 경로
        route.add(0); // 출발지
        dfs(info, route, 0, 0, 0); // dfs 탐색
        return ans;
    }
    
    static void dfs(int[] info, List<Integer> route, int node, int sheep, int wolf){
        // 해당 노드의 양 or 늑대의 수 갱신
        if(info[node]==0) sheep++;
        else wolf++;
        
        // 이동 불가능한 경우 리턴
        if(sheep <= wolf) return;
        
        // 이동 가능한 경우 최대값 갱신
        ans = Math.max(ans, sheep);
        
        List<Integer> next_route = new ArrayList<>(route); // 이전 부모에서 갈 수 있었던 모든 경로를 복사
        next_route.remove(Integer.valueOf(node)); // 현재 노드는 방문했으므로 삭제
        if(!arr[node].isEmpty()) next_route.addAll(arr[node]); // 현재 노드에서 갈 수 있는 모든 경로 추가
        
        for(int next : next_route){ // 과거에 갈 수 있었던 경로와, 현재 노드에서 갈 수 있는 경로 모두 탐색
            dfs(info, next_route, next, sheep, wolf);
        }
    }
}

 

코드가 생각보다 간단한데, 차근차근 분석해 보겠다.

 

1. 먼저 dfs 코드가 실행되면 해당 노드의 양 or 늑대의 수를 갱신해 준다.
2. 갱신이 완료되면 현재 노드 기준 이동 가능 여부를 확인한다.
3. 이동이 가능한 노드일 경우 최댓값을 갱신해 준다.
4. 이전(부모) 노드에서 갈 수 있는 모든 경로를 복사한다. (0->2->1을 하기 위해!)
5. 현재 노드는 방문했으므로 제거해 준다! (루프가 생기게 됨)
6. 현재 노드에서 갈 수 있는 경로들을 추가한다.
7. 현재 노드에서 이동할 수 있는 모든 경로를 dfs 탐색해 준다.
8. 모든 경로 탐색 후 ans를 출력한다.

핵심은 4번으로 이전 노드에서 가지 못한 노드를 재 탐색해 주는 과정을 꼭 처리해 주어야 문제를 해결할 수 있다!