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

작성일: 2024-12-04

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/92343

접근 방식

트리 모양이기에 단일 노드로 접근하되, 연결된 모든 노드를 탐색해야 하면서 백트래킹을 통해 상태를 관리해야 하기에 DFS를 사용해야 한다.

접근은 크게 세 가지로 나눌 수 있다.

늑대 수가 양의 수보다 크거나 같다면 방문 할 수 없음
현재 노드에서의 양 개수 갱신하기 (최댓값 유지)
현재 노드에서 연결된 노드 방문하기

잘못된 접근

import java.util.*;

class Solution {
    static int answer = -1;
    static LinkedList<Integer> list[];

    public int solution(int[] info, int[][] edges) {
        list = new LinkedList[info.length];

        // 노드 초기화
        for(int i=0; i<list.length; i++){
            list[i] = new LinkedList<>();
        }

        // 노드 연결
        for(int i=0; i<edges.length; i++){
            list[edges[i][0]].add(edges[i][1]);
        }

        // 방문 노드 관리를 위한 리스트
        List<Integer> tmp = new ArrayList<>();
        tmp.add(0);

        // 최대 양 개수 구하기
        dfs(new int[] {1, 0}, tmp, info);

        return answer;
    }

    void dfs(int[] status, List<Integer> next, int[] info){
        // 만약 현재 노드에서 양이 늑대보다 작거나 같다면 돌아가기
        if(status[0] <= status[1]){
            return;
        }

        // 양 개수 갱신
        answer = Math.max(answer, status[0]);

        // 방문 가능한 노드 탐색
        for(int i=0; i<next.size(); i++){
            int cur = next.get(i);

            // 현재 노드와 연결된 노드의 방문을 위한 리스트
            List<Integer> tmp = new ArrayList<>(next);
            tmp.remove(i);

            // 연결된 노드 중에 방문 예정에 포함되어 있지 않은 노드 추가
            for(int node:list[cur]){
                if(!tmp.contains(node)){
                    tmp.add(node);
                }
            }

            // 기존 상태와는 연결되지 않은 새로운 상태 배열 생성
            int[] newStatus = Arrays.copyOf(status, 2);

            // 현재 노드의 동물 여부에 따른 개수 추가
            if(info[cur]==0){
                newStatus[0]++;
            }else{
                newStatus[1]++;
            }

            // 새로운 상태와 노드로 다시 dfs
            dfs(newStatus, tmp, info);
        }
    }
}

먼저 List를 통해 방문 노드를 관리했다. 0번 노드는 무조건 양이기에, 0번에서 출발하는 것으로 정했다.

재귀호출이기에 기저조건을 설정해야 했는데, 접근 방식에서 말했듯이 양 수가 늑대 수 미만인 경우에만 DFS가 돌도록 했다.

하지만, 테스트 결과 정답이 아니었다. 코드를 여러 번 돌려보고, 디버깅을 해 본 결과
중복계산으로 인한 결과 오류임을 알게 되었다.

나는, DFS 진입 이전에 양과 늑대의 수를 설정하고, 방문 노드를 설정했다.
하지만, for문을 살펴보면 동물 여부에 따른 개수 추가 로직으로 인해 중복 계산이 발생했다.

처음 0번 노드를 발생할 때, 기저조건으로 인해 바로 return되는 것을 막기 위해 {1, 0}으로 설정했던 것이 문제였다.

따라서, 기저조건을 설정해서 탐색하는 것이 아니라, 상태 관리 이후에 탐색이 가능한 상태라면 탐색하는 것으로 변경하였다.

잘 된 접근

// 양이 늑대 초과라면 탐색
if(newStatus[0] > newStatus[1]){
    dfs(newStatus, tmp, info);
}

결과

소스 코드

import java.util.*;

class Solution {
    static int answer = -1;
    static LinkedList<Integer> list[];

    public int solution(int[] info, int[][] edges) {
        list = new LinkedList[info.length];

        // 노드 초기화
        for(int i=0; i<list.length; i++){
            list[i] = new LinkedList<>();
        }

        // 노드 연결
        for(int i=0; i<edges.length; i++){
            list[edges[i][0]].add(edges[i][1]);
        }

        // 방문 노드 관리를 위한 리스트
        List<Integer> tmp = new ArrayList<>();
        tmp.add(0);

        // 최대 양 개수 구하기
        dfs(new int[] {0, 0}, tmp, info);

        return answer;
    }

    void dfs(int[] status, List<Integer> next, int[] info){
        // 양 개수 갱신
        answer = Math.max(answer, status[0]);

        // 방문 가능한 노드 탐색
        for(int i=0; i<next.size(); i++){
            int cur = next.get(i);

            // 현재 노드와 연결된 노드의 방문을 위한 리스트
            List<Integer> tmp = new ArrayList<>(next);
            tmp.remove(i);

            // 연결된 노드 중에 방문 예정에 포함되어 있지 않은 노드 추가
            for(int node:list[cur]){
                if(!tmp.contains(node)){
                    tmp.add(node);
                }
            }

            // 기존 상태와는 연결되지 않은 새로운 상태 배열 생성
            int[] newStatus = Arrays.copyOf(status, 2);

            // 현재 노드의 동물 여부에 따른 개수 추가
            if(info[cur]==0){
                newStatus[0]++;
            }else{
                newStatus[1]++;
            }

            // 양이 늑대 초과라면 탐색
            if(newStatus[0] > newStatus[1]){
                dfs(newStatus, tmp, info);
            }

        }
    }
}

알게 된 점

DFS에서 기저조건을 설정할 때, 사전 계산이 필요하고 해당 계산으로 인해 결과값이 달라질 수 있는 경우에는

기저조건을 DFS 시작에 바로 설정하기 보다, 계산 이후 조건을 만족하는 경우에만 탐색하는 것을 통해 중복 계산을 방지할 수 있다.