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

1. 문제

---

프로그래머스

2. 풀이 과정

---

이 문제의 핵심 조건은 양 수가 늑대 수보다 많아야 한다는 것이다.

 

또한 주의해야할 점이 있는데, 루트 노드에서 왼쪽 오른쪽 중 한 곳을 정해 방문을 해도 그 다음, 그 아래 노드로만 갈 수 있는 것이 아닌 방문해왔던 윗 노드를 거쳐 다른 노드로도 갈 수 있다.

 

이게 무슨 말이냐면,

예를 들어서 0을 방문한 뒤 1을 방문하면 1에서 갈 수 있는 곳이 2,4 뿐만아니라 이전에 방문했던 0을 거쳐 다시 8로도 갈 수 있다.

즉, 1에선 2, 4, 8 노드와 인접해있다.

 

만약 0과 1을 방문한뒤 4를 방문했다면 4에선 3, 6 뿐 만아니라 1을 거쳐 2와 1,0을 거쳐 8로도 갈 수 있다. 

즉 4에선 3, 6, 2, 8 노드와 인접해있다는 소리이다.

 

이렇듯 이 문제는 양과 늑대 수에 주의하면서 인접한 노드를 모두 따져가며 최대 양의 수를 찾아야 한다.

 

이 문제를 풀기 위한 재료는 다음과 같다.

 

1. 트리를 표현하기 위한 인접리스트(배열, 포인터로도 구현 가능)

 

2. 현재 방문하고 있는 노드의 동물(양/늑대), 현재 방문 경로에 대한 늑대 수 , 양 수, 현재 노드에 대한 인접 노드에 대한 정보를 갖고 있는 노드 클래스 

 

0 - 1 - 4의 경로로 방문하는 경우에는 양 수가 2, 늑대 수가 1, 인접 노드가 2, 3, 6, 8이다.

 

0 - 1 - 8 - 7 - 9 - 4로 방문하는 경우 양 수가 4, 늑대 수가 2, 인접 노드가 2, 3, 6, 10, 11이 된다.

 

이렇 듯 같은 노드라 할지라도 방문하는 경로에 따라  늑대 수, 양 수, 인접 노드들은 모두 달라지게 된다. 그렇기 때문에 이러한 데이터를 하나로 묶을 수 있는 클래스를 하나 정의해야한다.

 

3. 현재 노드에서 방문이 가능한 인접 노드들을 저장할 큐

현재 노드에서 방문이 가능한 인접 노드들을 큐 자료구조에 저장하는 이유는 먼저 저장된 인접 노드를 먼저 방문해야하기 때문에 선입선출 자료구조인 큐를 사용해야 한다.

 

---

이제 문제를 풀어보자.

 

1.

루트 노드는 무조건 양이기 때문에 루트 노드를 큐에 넣는다.

큐에 저장할 때는 그냥 노드만 저장하는게 아니라 위에 2.에서 만들었던 노드 클래스를 저장해야 한다.

 

큐에서 데이터를 꺼낸다.

루트 노드인 0에선 1과 8에 인접해있지만 8로 가게되면 늑대 수와 양의 수가 1로 같아져 1로만 갈 수 있다.

따라서 1을 큐에 저장한다.

 

2. 

그 다음 다시 데이터 하나를 큐에서 꺼낸다.

큐에서 꺼낸 노드 1에선 2, 4, 8과 인접해있다. 

 

2, 4, 8 모두 늑대이지만 방문하더라도 양 2, 늑대 1이기 때문에 괜찮다. 모두 큐에 넣는다.

 

3.

큐에서 데이터를 하나꺼낸다.

이 데이터의 노드는 2고 인접노드는 4, 8인데 4, 8을 방문하게 되면 늑대 수가 양과 2로 같아진다. 

따라서 큐에 추가적으로 데이터를 넣지 않고 넘어간다.

 

다시 큐에서 데이터를 하나 꺼낸다. 

이 데이터의 노드는 4고 인접 노드는 2, 8, 3, 6인데 2, 8, 3, 6을 방문하게 되면 늑대 수가 양과 2로 같아진다.

따라서 여기서도 큐에 추가적으로 데이터를 넣지 않고 넘어간다.

 

마지막 데이터를 큐에서 꺼낸다. 

데이터의 노드는 8이고 인접 노드는 2, 4, 7, 9이다

2, 4의 경우 늑대이기 때문에 양2, 늑대2가 돼서 방문하지 못하게 된다. 그래서 넘어간다.

7, 9의 경우 양이다. 양3, 늑대1이 되기 때문에 방문이 가능하다. 그래서 큐에 넣어준다.

 

위의 과정을 큐가 빌 때까지 반복하면 된다.

그 때 양의 수가 이 문제의 정답이 된다.

 

이제 코드로 확인해보자

 

3. 내 코드

---

// 코드 출처: https://github.com/retrogemHK/codingtest_java/blob/main/solution/28.java
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashSet;

public class Solution {

    // 현재 위치, 양의 수, 늑대의 수, 인접 노드 저장을 위한 클래스
    private static class Info {
        int node, sheep, wolf;
        HashSet<Integer> adjacent;

        public Info(int node, int sheep, int wolf, HashSet<Integer> adjacent) {
            this.node = node;
            this.sheep = sheep;
            this.wolf = wolf;
            this.adjacent = adjacent;
        }
    }

    private static ArrayList<Integer>[] tree; // 트리 정보를 저장할 인접리스트

    // ❶ 트리 구축 메소드
    private static void buildTree(int[] info, int[][] edges) {
        tree = new ArrayList[info.length];
        for (int i = 0; i < tree.length; i++) {
            tree[i] = new ArrayList<>();
        }

        for (int[] edge : edges) {
            tree[edge[0]].add(edge[1]);
        }
    }

    public int solution(int[] info, int[][] edges) {
        buildTree(info, edges); // ❷ 트리 생성

        int answer = 0; // ❸ 최대 양의 수를 저장할 변수

        // ❹ 큐 생성 및 초기 상태 설정
        ArrayDeque<Info> queue = new ArrayDeque<>();
        queue.add(new Info(0, 1, 0, new HashSet<>()));

        
        while (!queue.isEmpty()) {
            // ❺ 큐에서 현재 상태를 꺼냄
            Info now = queue.poll();
            // ❻ 최대 양의 수 업데이트
            answer = Math.max(answer, now.sheep);
            // ❼ 인접한 노드 집합에 현재 노드의 이웃 노드 추가
            now.adjacent.addAll(tree[now.node]);

            // ❽ 인접한 노드들에 대해 탐색
            for (int next : now.adjacent) {
                // ❾ 기존 해시셋의 데이터를 복사하고 현재 방문한 정점을 해시셋에서 제거
                HashSet<Integer> set = new HashSet<>(now.adjacent);
                set.remove(next);

                if (info[next] == 1) { // ➓ 늑대일 경우
                    if (now.sheep != now.wolf + 1) {
                        queue.add(new Info(next, now.sheep, now.wolf + 1, set));
                    }
                }
                else { // ⓫ 양일 경우
                    queue.add(new Info(next, now.sheep + 1, now.wolf, set));
                }
            }
        }

        return answer;
    }

}

시간 복잡도

• O(N^2)

 

4. 피드백

---

• 선입선출 자료구조는 큐