[프로그래머스]2022 KAKAO BLIND RECRUITMENT - 양과 늑대 - 자바(JAVA)

https://programmers.co.kr/learn/courses/30/lessons/92343

코딩테스트 연습 - 양과 늑대

 

문제 해석

이진트리 모양 각 노드에 늑대와 양이 한 마리씩 놓여 있습니다.

각 노드를 돌아다니며 양을 모으려 합니다.

각 노드를 방문할 때 마다 해당 노드에 있던 양과 늑대가 따라옵니다.

이때, 늑대는 양을 잡아먹을 기회를 노리고 있으며 양 <= 늑대가 되면 바로 모든 양을 잡아먹습니다.

중간에 양이 늑대에게 잡아먹히지 않도록 하면서 최대한 많은 수의 양을 모아 다시 루트 노드로 돌아오려고 합니다.

 

문제 풀이 전 설계

우선 방문했던 노드를 다시 방문할 수 있을 것 같습니다.

문제의 핵심은 우선  양 <= 늑대가 될 수 있다면 그 시점에는 방문하지 않아야 하며, 이후에 양의 개수가 많아져서 방문할 수 있다면 방문할 수 있어야 합니다.

 

문제의 info길이는 17이며 이진트리의 형태를 띠기 때문에 DP까지는 활용하지 않아도 될 것 같다는 생각이 듭니다.

만약 현재 노드 아래의 양과 늑대의 개수를 기록해서 이를 활용한다면 양이나 늑대에 도달할 때 계속 부모 노드들까지 모두 갱신해 주어야 합니다

 

문득 BFS를 활용하는데 양인 경우가 우선순위를 가지도록 하면 어떨까?라는 생각이 들었습니다.

0에서 시작하고 양의 개수는 1개를 가집니다. Queue에 1과 8이 후보로 들어갑니다.

이때 8은 늑대 >= 양의 개수가 되기 때문에 더 이상 갈 수 없지만 1은 갈 수 있습니다.

1은 양의 개수 2개를 가지고 다시 BFS를 돕니다. Queue에 0, 2, 4가 후보로 들어갑니다.

2번은 더 이상 갈 곳이 없고 양이 없기 때문에 더 이상 탐색하지 않습니다.

4번은 3,6번을 더 탐색할 수 있는데 이러는 순간 늑대의 개수가 2개로 양의 개수와 동일해지기 때문에 더 이상 탐색하지 않습니다.

그러면 0번만 남았습니다. 0번은 양의 개수가 2개가 되어 이제 8로 이동할 수 있습니다.

늑대의 개수를 +1시 키고 7~9에 방문하여 양의 개수를 증가시킵니다.

이런 식으로 탐색하면 양 다섯 마리를 모두 찾을 수 있습니다.

하지만 시간 초과가 좀 걱정됩니다

 

또한 이 문제에서 트리를 구성하는데 규칙이 없기 때문에 직접 연결해줘야 합니다.

 

 

문제 해설

우선 백 트레킹으로 구현 시 n=17인 완전 이진트리에서는 시간 초과가 발생할 수 있습니다.

하지만 TC가 빈약해 통과가 가능하다고 합니다.

 

비트 마스킹으로 표현한다면 2^17이 많아 보이지만 사실 계산해보면 131072입니다.

따라서 17개의 비트로 방문 체크를 하면서 BFS, DFS를 한다면 풀이가 가능할 것 같습니다.

 

해당 풀이는 DFS + BFS입니다.

 

이때 트리는 HashMap <Integer, ArrayList <Integer>>를 이용하여 구성합니다.

이때 방문 체크를 HashSet을 이용하여 해 줍니다.

 

트리를 구성하는것도 이해가 편하게 됬으며, 값을 갱신하고 비트마스킹으로 방문체크를 하는과정도 이해가 잘 되었습니다.

 

하지만 의문점이 트리노드를 자식으로만 가진다면 0 -> 1으로 이동했을때 다시 0으로 갔다가 8번으로 이동은 어떻게 하는거지? 라는 생각을 가지고있었습니다.

 

이때 그 과정을 for(int i=0; i<size; i++)을 사용하여 그냥 모든노드에 대해서 다시 탐색해보면서 해결했다고 이해했습니다.

 

결국에는 DFS를 탐색하는 과정에서 비트마스킹이 채워지고 그 결과에 대해서 모든노드에 대해서 겹치지 않는 부분을 다시 탐색하면서 가보지 않았던 부분들을 탐색할 수 있게 됩니다.

 

코드

import java.util.*;

class Solution {
    int[] info;
    HashMap<Integer, ArrayList<Integer>> tree = new HashMap<>();
    HashSet<Integer> set = new HashSet<>();
    int answer = 1;
    int size;
    
    public int solution(int[] info, int[][] edges) {
        this.info = info;
        size = info.length;

        for(int[] e : edges) {
            if(!tree.containsKey(e[0])) {
                tree.put(e[0], new ArrayList<>());
            }
            tree.get(e[0]).add(e[1]);
        }
        
        visit(1, 1, 0); // 첫번째 노드는 방문
        
        return this.answer;
    }
    
    public void visit(int visited, int sheep, int wolf) {
        if(sheep - wolf == 0) return;
        else {
            answer = Math.max(sheep, answer);
        }
        
        for(int i = 0; i < size; i++) {
            
            // 현재 방문한 상태이고 && 다음에 방문 가능한 노드가 존재할 때
            if(((1 << i) & visited) != 0 && tree.containsKey(i)) {
                ArrayList<Integer> a = tree.get(i);
                
                for(int j = 0; j < a.size(); j++) {
                    int next = a.get(j);
                    
                    // 다음 노드를 이전에 방문한 적이 없을 때
                    if((visited & (1 << next)) == 0) {
                        int v = visited | (1 << next);
                        
                        if(set.contains(v)) continue; // 이전에 계산
                        
                        set.add(v);
                        if(info[next] == 0) visit(v, sheep + 1, wolf);
                        else visit(v, sheep, wolf + 1);
                    }
                }
            }
        }
    }
}

 

 

 

출처

https://www.youtube.com/watch?v=caGtdr3_nxs (양과 늑대 : 18분부터 시작)

https://jangcenter.tistory.com/120

Programmers - 양과 늑대(Java)

https://sdardew-valley.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%96%91%EA%B3%BC-%EB%8A%91%EB%8C%80-Java

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