문제 링크

첫번째 시도

• 반례 두개를 찾지 못해서 틀렸다.

코드

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

class SheepAndWolf {
    int sheep;
    int wolf;
    String route;

    public SheepAndWolf(int sheep, int wolf, String route) {
        this.sheep = sheep;
        this.wolf = wolf;
        this.route = route;
    }
}

public class Solution {
    public int solution(int[] info, int[][] edges) {
        int answer = 1;
        Queue<SheepAndWolf> que = new LinkedList<>();
        que.offer(new SheepAndWolf(1, 0, "0"));

        ArrayList<ArrayList<Integer>> graph = createGraph(info, edges);
//        for (ArrayList<Integer> arr : graph) {
//            for (int i : arr) {
//                System.out.print(i);
//            }
//            System.out.println();
//        }
        while (!que.isEmpty()) {
            SheepAndWolf now = que.poll();

            for (String nowNodeStr : now.route.split(" ")) {
                for (int nextNode : graph.get(Integer.parseInt(nowNodeStr))) {
                    // nextNode가 route에 포함된 경우 방문 x
                    if (now.route.contains(String.valueOf(nextNode))) {
                        continue;
                    }
                    System.out.println(now.route + "->" + nextNode + ", sheep:" + now.sheep + ", wolf:" + now.wolf + ", answer:" + answer);
                    // 다음 노드가 양인 경우
                    if (info[nextNode] == 0) {
                        int nextSheep = now.sheep + 1;
                        answer = Math.max(answer, nextSheep);
                        que.offer(new SheepAndWolf(nextSheep, now.wolf, now.route + " " + nextNode));
                    } else {
                        // 양 <= 늑대일 경우 갈 수 없음
                        if (now.sheep > now.wolf + 1) {
                            que.offer(new SheepAndWolf(now.sheep, now.wolf + 1, now.route + " " + nextNode));
                        }
                    }
                }
            }
        }

        return answer;
    }

    private ArrayList<ArrayList<Integer>> createGraph(int[] info, int[][] edges) {
        ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
        int len = info.length;
        for (int i = 0; i <= len; i++) {
            graph.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
        }
        return graph;
    }
}

풀이

• 지나온 경로를 문자열 형태로 저장하는 방식으로 풀었다.

두번째 시도

• 맞았다.

코드

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

class SheepAndWolf {
    int sheep;
    int wolf;
    ArrayList<Integer> route;

    public SheepAndWolf(int sheep, int wolf, ArrayList<Integer> route) {
        this.sheep = sheep;
        this.wolf = wolf;
        this.route = route;
    }
}

class Solution {
    public int solution(int[] info, int[][] edges) {
        int answer = 1;
        Queue<SheepAndWolf> que = new LinkedList<>();

        ArrayList<ArrayList<Integer>> graph = createGraph(info, edges);
//        for (ArrayList<Integer> arr : graph) {
//            for (int i : arr) {
//                System.out.print(i);
//            }
//            System.out.println();
//        }

        ArrayList<Integer> firstRoute = new ArrayList<>();
        for (int i : graph.get(0)) {
            firstRoute.add(i);
        }
        SheepAndWolf startSheepAndWolf = new SheepAndWolf(1, 0, firstRoute);
        que.offer(startSheepAndWolf);

        while (!que.isEmpty()) {
            SheepAndWolf now = que.poll();
            if (now.sheep <= now.wolf) {
                continue;
            }
            answer = Math.max(answer, now.sheep);
//            for (int i : now.route) {
//                System.out.print(i + " ");
//            }
//            System.out.println("->" + ", sheep:" + now.sheep + ", wolf:" + now.wolf + ", answer:" + answer);
            // 나아 갈 수 있는 경우를 큐에 삽입
            for (int nowNode : now.route) {
                int nextSheep = now.sheep + (info[nowNode] ^ 1);
                int nextWolf = now.wolf + info[nowNode];
                ArrayList<Integer> nextRoute = new ArrayList<>();
                nextRoute.addAll(now.route);
                nextRoute.remove(Integer.valueOf(nowNode));
                for (int nextNode : graph.get(nowNode)) {
                    nextRoute.add(nextNode);
                }
                que.offer(new SheepAndWolf(nextSheep, nextWolf, nextRoute));
            }

        }

        return answer;
    }

    private ArrayList<ArrayList<Integer>> createGraph(int[] info, int[][] edges) {
        ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
        int len = info.length;
        for (int i = 0; i <= len; i++) {
            graph.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
        }
        return graph;
    }

}

풀이

• 갈 수 있는 경로를 저장하는 방식으로 푸니 맞았다.

핵심 제한 사항
2 ≤ info의 길이 ≤ 17

info의 max값이 상당히 작으므로, 모든 노드를 살펴봐도 시간 제한이 걸릴 것 같지 않다. dfs와 bfs 둘다 사용 가능해 보이며, 나는 bfs를 사용하여 풀었다.
여기서 핵심 포인트는 각 루트가 서로 영향을 주지 않게 새로 생성해서 대입해야 한다.