[프로그래머스/Java] Lv.3 - 양과 늑대

승래·2026년 4월 2일

프로그래머스 Lv.3 - 양과 늑대

요구사항

루트(0번)에서 시작해서 트리를 탐색하며 최대한 많은 양을 모으는 문제
늑대 수 >= 양 수가 되는 순간 양을 모두 잃음
한번 지나친 노드로 다시 돌아갈 수 있음

접근 방식

BFS + canVisit 상태 관리 로 풀었다.

핵심 아이디어

방문 처리를 하지 않고 "지금 방문 가능한 노드 목록"을 상태로 관리

현재 canVisit = [1, 2]
→ 1 선택 시:
  canVisit에서 1 제거 → [2]
  1의 자식 추가 → [2, 3, 4]
  → 나중에 2로도 갈 수 있음!

왜 canVisit이 필요한가?

단순 BFS로 풀면:
→ 한번 지나친 노드의 형제들을 나중에 방문 못함
→ 모든 경우의 수 탐색 불가

canVisit으로 풀면:
→ 현재 상태에서 갈 수 있는 모든 노드를 들고 다님
→ 어떤 순서로든 방문 가능 ✅

늑대 이동 조건

sheep > wolf + 1 일 때만 늑대 노드로 이동 가능
(이동 후 wolf+1이 되어도 sheep이 더 많아야 함)

코드

import java.util.*;

class State {
    int vex, sheep, wolf;
    List<Integer> canVisit;

    public State(int vex, int sheep, int wolf, List<Integer> canVisit) {
        this.vex = vex; this.sheep = sheep;
        this.wolf = wolf; this.canVisit = canVisit;
    }
}

class Solution {
    ArrayList<ArrayList<Integer>> graph;
    int answer;

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

        graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
        for (int[] x : edges) graph.get(x[0]).add(x[1]); // 단방향!

        bfs(info);
        return answer;
    }

    public void bfs(int[] info) {
        Queue<State> q = new LinkedList<>();
        q.offer(new State(0, 1, 0, graph.get(0)));

        while (!q.isEmpty()) {
            State s = q.poll();
            answer = Math.max(answer, s.sheep);

            for (int next : s.canVisit) {
                List<Integer> newCanVisit = new ArrayList<>(s.canVisit);
                newCanVisit.remove(Integer.valueOf(next));
                newCanVisit.addAll(graph.get(next));

                if (info[next] == 0) {
                    q.offer(new State(next, s.sheep+1, s.wolf, newCanVisit));
                } else {
                    if (s.sheep <= s.wolf + 1) continue;
                    q.offer(new State(next, s.sheep, s.wolf+1, newCanVisit));
                }
            }
        }
    }
}