프로그래머스 - 양과 늑대

⭐ 오늘의 문제

1. 문제 요약

문제 규칙

• 1. 이진트리로 구성되었고, 각 노드는 양 또는 늑대가 있다.
• 2. 해당 노드에 가면 양 or 늑대가 tree 순회가 끝날때까지 따라온다.
• 3. 현재 따라오는 양 <= 현재 따라오는 늑대 가 되면 게임이 끝난다.

출력

• 최대 양의 개수를 구하라.

2. 문제 접근

해당 문제의 가장 까다로운 점은, 바로 현재 노드의 왼쪽 자식들을 순회하다, 중간에 멈추고 현재 노드의 오른쪽 자식들을 순회하는 경우가 존재한단 것이다.

즉 다음과 같이 현재 노드를 움직여 줘야 한단 뜻이다! 이걸 어떻게 구현할 것인가

DFS + 인자로 다음 위치 리스트 넘겨주기

를 사용하면 가능해진다. 정확한 로직 설계는 다음과 같다.

1) 현재 노드가 양인지, 늑대인지 판단해 카운팅
2) 현재까지 따라온 늑대 >= 현재까지 따라온 양 인 경우 DFS 탐색 바로 종료
3) 이전 재귀함수에서 넘어온 다음 위치 리스트(lsit_1)를, 현재 위치 기준 다음 위치 리스트(list_2)에 일단 넣음
4) list_1에는 당연하게도 현재 위치 노드가 들어있을 것. 현재 노드는 list_2에서 지워줌
- 이미 현재 노드에는 와 있는 상태이니까!
5) 현재 노드의 자식들도 list_2에 넣음
6) list_2의 모든 위치에 대해 dfs실행

그렇다면 다음과 같이 dfs가 동작하게 된다.

3. 코드

import java.io.*;
import java.util.*;

class Solution {
    static List<Integer> [] tree;
    static int maxSheep;
    static int [] info;
    public int solution(int[] info, int[][] edges) {
        tree = new List[info.length];
        this.info=info;
        
        for(int i=0; i<info.length; i++){
            tree[i] = new ArrayList<>();
        }
        
        for(int i=0; i<edges.length; i++){
            tree[edges[i][0]].add(edges[i][1]);
        }
        
        List <Integer> next = new ArrayList<>();
        next.add(0);
        dfs(0,0,0,next);
        return maxSheep;
    }
    
    static void dfs(int now, int sheep, int woolf, List <Integer> next){
        if (info[now] == 0) {
            sheep++;
        } else {
         woolf++;
        }
        
        if(woolf>=sheep) return;
        maxSheep = Math.max(sheep, maxSheep);
        
        List<Integer> list = new ArrayList<>();
        
        list.addAll(next);
        list.remove(Integer.valueOf(now));
        
        for(int value : tree[now]) {
            list.add(value);
        }
        
        for(int value : list) {
            dfs(value, sheep, woolf, list);
        }
        
    }
}

어떻게 하면 왼쪽 자식과 오른쪽 자식을 번갈아 탐색하지..? 라고 생각했는데 또 배워가는 문제였던 것 같다.

비슷한 문제를 또 풀어보고 싶다. 끝~