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

Notice

• 다른 코딩 문제 풀이는 코딩 문제 풀이 문서 참고

문제 정보

• 문제 링크
• 난이도: Lv.3
• 문제 유형: 탐색, 자료구조

해설

Notice

이하의 내용은 카카오테크 공식 홈페이지의 해설과 해당 해설을 보고 정리한 내용을 바탕으로 작성됨

사실 그렇게 어렵지 않은 문제다.

입력 크기가 작기 때문에 DFS를 활용한 완전 탐색으로 충분히 풀 수 있다.

다만 일반적인 DFS와는 달리 자식 노드를 순차적으로 탐색하면 안된다.

예를 들어, 루트 노드 0의 자식 노드가 1과 2가 있다고 할 때 0 → 1과 0 → 2 모두 살펴봐야 하기 때문이다. 또한 당연한 말이지만, 각각의 경우의 “다음으로 방문 가능한 노드 집합”이 다르다. 그러므로 “다음으로 방문 가능한 노드 집합”을 새로 만들어야 한다.

코드

import java.util.*;
 
class Solution {
    List<List<Integer>> adj;
    int maxSheep = 0;
    public int solution(int[] info, int[][] edges) {
        adj = new ArrayList<>();
        for(int i = 0; i < info.length; i++)
            adj.add(new ArrayList<>());
        
        for(int[] edge: edges) 
            adj.get(edge[0]).add(edge[1]);
        
        Set<Integer> next = new HashSet<>();
        
        dfs(0, 0, 0, next, info);
        
        return maxSheep;
    }
    
    private void dfs(int cur, int sheep, int wolf, Set<Integer> nextNodes, int[] info) { 
        if (info[cur] == 0) 
            sheep += 1;
        else
            wolf += 1;
        
        if (sheep <= wolf)
            return;
        
        maxSheep = Math.max(maxSheep, sheep);
        
        Set<Integer> newNextNodes = new HashSet<>(nextNodes);
        newNextNodes.remove(cur);
        
        for(int child : adj.get(cur)) 
            newNextNodes.add(child);
        
        for(int next : newNextNodes) {
            dfs(next, sheep, wolf, newNextNodes, info);
        }
            
        return;
    }
}

구현 중 트러블 슈팅

• DFS 구현
  • DFS를 활용한 완전 탐색이라길래 습관처럼 순차적으로 탐색하도록 했다가 틀렸다.

후기

• 문제를 잘못 이해했다. (늑대의 수도 누적된다는 걸 몰랐음.)
• 문제를 너무 어렵게 생각했다.
  • 노드의 최대 개수가 17개라 완전 탐색해도 무방한데 이를 간과하고 백트래킹으로 풀려고 했다. ¹

Footnotes

1. 백트래킹으로는 안되나? 싶어서 Claude에 물어봤는데 “가능은 하지만 비효율적이고 오버 엔지니어링”이라고 한다. 다만 입력이 커지면 백트래킹이 더 유리하다는데, 답변 중에 계속 말이 바뀌어서 적당히 걸러들어야 할 듯하다. (n = 30 ~ 50에서 효율적 → n = 25 ~ 40에서 효율적 → n = 20 ~ 40에서 효율적) ↩