[프로그래머스/Java] 92343번 양과 늑대

프로그래머스 양과 늑대 [2022 KAKAO BLIND RECRUITMENT]
https://programmers.co.kr/learn/courses/30/lessons/92343

info의 길이가 17로 크지 않아 DFS 기반의 완전탐색에 방점을 찍고 접근했다.
다만 알고리즘을 채택한다고 다가 아니었으니, 걸리는 점이 매우 많았다.

• 양 쪽 자식 노드에 모두 방문해야 할 수 있기 때문에 이미 방문한 노드에 다시 방문할 수 있어야 하고,
• 재방문하는 경우에는 양/늑대 수를 갱신하지는 않는다.
• 재방문은 가능하면서 무한루프에 빠져서는 안되므로, 적당히 빠져나올 조건이 필요하다 등등.

고민 하나하나를 조건문으로 만들어 코드에 집어넣다보니 코드는 지저분해졌고, 오히려 답이 나오지 않았다.
결국 다른 분들의 코드를 읽고 문제 풀이의 단서를 찾았다. 정리하자면 다음과 같다.

이미 방문한 노드 사이에서는 자유로운 이동이 가능하므로, 여기에 대한 경로 탐색은 하지 않을 것.
방문한 노드를 통해 새롭게 갈 수있는 노드에 대해서만 고민할 것.

import java.util.*;
class Solution {
    public int solution(int[] info, int[][] edges) {
        
        List<Integer>[] childList = new ArrayList[info.length];
        
        for(int i = 0 ; i < info.length ; i++)
            childList[i] = new ArrayList<>();
        
        for(int[] edge : edges)
            childList[edge[0]].add(edge[1]);
        
        List<Integer> list = new ArrayList<>();
        list.add(0);

        return dfs(info, childList, list, new int[2], 0);
    }
    
    public int dfs(int[] info, List<Integer>[] childList, List<Integer> list, int[] count, int index){
        
        count[info[index]]++;
        int result = count[0];
        
        if(count[1] < count[0]){
            List<Integer> newList = new ArrayList<>();
            newList.addAll(list);
            newList.addAll(childList[index]);
            newList.remove(Integer.valueOf(index));

            for(Integer tmp : newList)
                result = Math.max(result, dfs(info, childList, newList, count, tmp));
        }
        count[info[index]]--;
        return result;
    }
}

코드에서 인수로 넘겨주는 newList가 위에서 말한 '방문한 노드를 통해 새롭게 갈 수 있는 노드'이다.

자잘한 경로 탐색에 대한 집착을 버리니 코드는 심플해졌다.
늑대와 양의 수를 비교하는 로직 말고는 if문도 쓰이지 않았다.

알고리즘을 복잡하게 생각할 수록 코드는 길어지고, 오히려 스스로 함정을 만들어 빠지기 쉬운 듯 하다.

.
.

2022 KAKAO BLIND RECRUITMENT의 Lv.3 문제들을 오늘자로 다 풀어보게 되었다.

첫인상에서 꽤 당황스러웠던 문제들이지만 의외로 어려운 알고리즘을 필요로 하지 않았다.
가진 지식 자체보다 응용 능력과, 구현 능력을 보는구나 싶었던 문제들이었다.

알고리즘 문제를 푸는 데 별로 집중하지 못했던 요즘이다.
남은 봄 안에 부지런히 풀 수 있기를.