[JAVA] 프로그래머스 (Lv.3) 양과 늑대

링크

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

---

입력 예제

int[] info = [0,0,1,1,1,0,1,0,1,0,1,1]
int[][] edges = [[0,1],[1,2],[1,4],[0,8],[8,7],[9,10],[9,11],[4,3],[6,5],[4,6],[8,9]]

---

출력 예제

5

---

풀이

루트 노드부터 시작하여 탐색을 하며 양의 수와 늑대 수를 카운트하여 양의 수가 최대가 될 때를 구해야 한다. 모든 가능한 경우의 수에 대해 탐색하며 불가능한 경우는 가지치기를 하며 양의 수를 갱신해나간다.

입력 예제의 경우 우선 루트 노드부터 탐색한다. 루트 노드의 자식 노드는 1번과 8번인데 1번은 양이므로 계속해서 탐색이 가능하지만, 8번은 늑대이므로 양과 늑대의 수가 같아지므로 바로 탐색할 수 없다.

• 0 - 1 (양 2마리)
• 0 - 8 (양 1마리, 늑대 1마리) -> 불가

하지만 탐색을 하면서 루트 노드로 돌아올 수 있으므로 매번 모든 노드에 대해서 탐색을 해야 한다. 현재 0번과 1번을 방문한 상태에서는 양이 2마리이므로 8번 노드에 대해서 탐색이 가능하다.

• 0 - 1 - 8 (양 2마리, 늑대 1마리)

이런 식으로 방문 여부로 백트래킹을 진행하며 매번 방문한 경우에 대해 탐색을 한다.

private void dfs(int sheep, int wolf) {
    if (sheep <= wolf) {  //양이 늑대보다 작거나 같으면 중지
        return;
    }
    
    //방문한 노드를 기준으로 가능한 모든 경로 탐색
    for (int cur = 0; cur < n; cur++) {
        if (visited[cur]) {
            for (Integer next : adjList.get(cur)) {  //자식 노드 탐색
                if (!visited[next]) {  //방문하지 않은 노드일 때
                    visited[next] = true;
                    
                    if (info[next] == 0) {  //양 카운트
                        dfs(sheep + 1, wolf);
                    } else {  //늑대 카운트
                        dfs(sheep, wolf + 1);
                    }
                    
                    visited[next] = false;  //백트래킹
                }
            }
        }
    }
    maxSheep = Math.max(maxSheep, sheep);
}

위에선 boolean 배열으로 각 노드의 방문 여부를 체크하고 방문한 노드의 자식 노드를 탐색하는 식으로 백트래킹을 구현했다. 이와 비슷하게 방문한 노드를 리스트에 저장하여 경로에 포함된 노드에 대해서 자식 노드를 탐색하는 식으로도 구현할 수 있다.

private static void dfs(int sheep, int wolf, List<Integer> path) {
    if (sheep <= wolf) {  //양이 늑대보다 작거나 같으면 중지
        return;
    }
    
    //현재 경로로 가능한 모든 경로 탐색
    for (int i = 0; i < path.size(); i++) {
        int cur = path.get(i);
        
        for (int next : adjList.get(cur)) {  //자식 노드 탐색
            if (!path.contains(next)) {  //경로에 포함되지 않은 노드일 경우
                path.add(next);
                
                if (info[next] == 0) {  //0 -> 양 카운트
                    dfs(sheep + 1, wolf, path);
                } else {  //1 -> 늑대 카운트
                    dfs(sheep, wolf + 1, path);
                }
                
                path.remove(path.size() - 1);  //백트래킹
            }
        }
    }
    
    maxSheep = Math.max(maxSheep, sheep);
}

전체 코드

import java.util.ArrayList;
import java.util.List;

/*
프로그래머스 / 양과 늑대 / Level 3
https://school.programmers.co.kr/learn/courses/30/lessons/92343
 */
class Solution {

    private static List<List<Integer>> adjList = new ArrayList<>();
    private static int[] info;
    private static int n, maxSheep;
    private static boolean[] visited;

    public int solution(int[] info, int[][] edges) {
        this.info = info;
        n = info.length;

        for (int i = 0; i < n; i++) {
            adjList.add(new ArrayList<>());
        }

        for (int[] edge : edges) {
            adjList.get(edge[0]).add(edge[1]);
        }

        visited = new boolean[n];
        visited[0] = true;  //루트 노드
        dfs(1, 0);

        return maxSheep;
    }

    private static void dfs(int sheep, int wolf, List<Integer> path) {
        if (sheep <= wolf) {  //양이 늑대보다 작거나 같으면 중지
            return;
        }

        //현재 경로로 가능한 모든 경로 탐색
        for (int i = 0; i < path.size(); i++) {
            int cur = path.get(i);

            for (int next : adjList.get(cur)) {
                if (!path.contains(next)) {
                    path.add(next);

                    if (info[next] == 0) {  //0 -> 양 카운트
                        dfs(sheep + 1, wolf, path);
                    } else {  //1 -> 늑대 카운트
                        dfs(sheep, wolf + 1, path);
                    }

                    path.remove(path.size() - 1);
                }
            }
        }

        maxSheep = Math.max(maxSheep, sheep);
    }

    private void dfs(int sheep, int wolf) {
        if (sheep <= wolf) {  //양이 늑대보다 작거나 같으면 중지
            return;
        }

        //방문한 노드를 기준으로 가능한 모든 경로 탐색
        for (int cur = 0; cur < n; cur++) {
            if (visited[cur]) {
                for (Integer next : adjList.get(cur)) {  //자식 노드 탐색
                    if (!visited[next]) {  //방문하지 않은 노드일 때
                        visited[next] = true;

                        if (info[next] == 0) {  //양 카운트
                            dfs(sheep + 1, wolf);
                        } else {  //늑대 카운트
                            dfs(sheep, wolf + 1);
                        }

                        visited[next] = false;  //백트래킹
                    }
                }
            }
        }

        maxSheep = Math.max(maxSheep, sheep);
    }
}