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

출처

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

프로그래머스

문제

 

주어지는 트리의 각 노드에는 양과 늑대 둘중 하나가 놓여져 있다. 노드를 돌아다니며 양과 늑대를 데리고 다니는데, 늑대가 양보다 많아지면 늑대가 양을 모두 잡아먹게 된다. 이 조건에 따라 각 노드를 순회하며 모을 수 있는 양의 최대 마릿수를 구하는 문제이다.

 

풀이

처음에 이 문제를 일반적인 DFS 또는 백트래킹으로만 해결하려고 하였다. 하지만 한번 방문했던 노드도 다시 방문 해야하는 경우가 많기 때문에 불가능 하다. 예를 들면, 위 예제에서, 0 -> 8 -> 7을 탐색한 후 다른 노드로 탐색할 수 있기 때문이다. 따라서 DFS 경로 보다는, 다른 접근 방법을 생각해 보았다.

 

양의 최대가 되도록 방문 순서를 정하기 위해서는 결국, 모든 경로의 조합을 만든 뒤 그 순서대로 방문해보며 완전 탐색을 진행하는것이 필요하다. 다만, 우리는 필요없는 모든 경우를 제외해 시간초과를 막아야 한다.

 

먼저, 양의 마릿수 보다 늑대의 마릿수가 많아지는 시점에 더이상 탐색을 진행하지 않아야 한다. 이때 양의 마릿수는 0이 되기 때문에 탐색이 불필요하다. 

 

다음으로, 방문 경로의 조합을 만들 때 부모를 방문하고 자식이 방문되지 않은 경우만 고려한다. 예를 들어 0 -> 9 관계가 있다면 부모인 0을 방문하지 않았다면 9는 방문할 수 없다.

 

이렇게 유망하지 않으면 되돌아가는 backtracking과, 조합을 구하는 dfs를 모두 사용하여 문제를 해결할 수 있었다. 아래 코드를 보면 보다 더 자세히 이해할 수 있을 것이다.

 

코드

import java.util.*;
class Solution {
    boolean[] visited;
    
    public int solution(int[] info, int[][] edges) {
        visited = new boolean[info.length];
        visited[0] = true;
        return dfs(info, edges, 1, 0);
    }
    
    public int dfs(int[] info, int[][] edges, int sheep, int wolf) {
        if (sheep == wolf) return sheep;
        int maxSheep = sheep;
        
        for (int[] edge : edges) {
            int p = edge[0];
            int c = edge[1];
            if (visited[p] && !visited[c]) {
                visited[c] = true;
                if (info[c] == 0) {
                    maxSheep = Math.max(maxSheep, dfs(info, edges, sheep+1, wolf));
                } else {
                    maxSheep = Math.max(maxSheep, dfs(info, edges, sheep, wolf+1));
                }
                visited[c] = false;
            }
        }
        return maxSheep;
        
    }

}