[programmers] 양과 늑대

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

프로그래머스

2진 트리 모양 초원의 각 노드에 늑대와 양이 한 마리씩 놓여 있습니다. 이 초원의 루트 노드에서 출발하여 각 노드를 돌아다니며 양을 모으려 합니다. 각 노드를 방문할 때마다 해당 노드에 있던 양과 늑대가 당신을 따라오게 됩니다. 이때, 늑대는 양을 잡아먹을 기회를 노리고 있으며, 당신이 모은 양의 수보다 늑대의 수가 같거나 더 많아지면 바로 모든 양을 잡아먹어 버립니다. 당신은 중간에 양이 늑대에게 잡아먹히지 않도록 하면서 최대한 많은 수의 양을 모아서 다시 루트 노드로 돌아오려 합니다.

 

예를 들어, 위 그림의 경우(루트 노드에는 항상 양이 있습니다) 0번 노드(루트 노드)에서 출발하면 양을 한마리 모을 수 있습니다. 다음으로 1번 노드로 이동하면 당신이 모은 양은 두 마리가 됩니다. 이때, 바로 4번 노드로 이동하면 늑대 한 마리가 당신을 따라오게 됩니다. 아직은 양 2마리, 늑대 1마리로 양이 잡아먹히지 않지만, 이후에 갈 수 있는 아직 방문하지 않은 모든 노드(2, 3, 6, 8번)에는 늑대가 있습니다. 이어서 늑대가 있는 노드로 이동한다면(예를 들어 바로 6번 노드로 이동한다면) 양 2마리, 늑대 2마리가 되어 양이 모두 잡아먹힙니다. 여기서는 0번, 1번 노드를 방문하여 양을 2마리 모은 후, 8번 노드로 이동한 후(양 2마리 늑대 1마리) 이어서 7번, 9번 노드를 방문하면 양 4마리 늑대 1마리가 됩니다. 이제 4번, 6번 노드로 이동하면 양 4마리, 늑대 3마리가 되며, 이제 5번 노드로 이동할 수 있게 됩니다. 따라서 양을 최대 5마리 모을 수 있습니다.

 

각 노드에 있는 양 또는 늑대에 대한 정보가 담긴 배열 info, 2진 트리의 각 노드들의 연결 관계를 담은 2차원 배열 edges가 매개변수로 주어질 때, 문제에 제시된 조건에 따라 각 노드를 방문하면서 모을 수 있는 양은 최대 몇 마리인지 return 하도록 solution 함수를 완성해 주세요.

 

제한사항

 

입출력 예

---

접근방법

1. 어떤 알고리즘을 써야 할까? 완전탐색 그중에서 백트래킹을 통해 최대한 모을 수 있는 양을 찾도록 하겠습니다.

2. 주어진 edges를 통해 인접리스트 생성

3. visited 배열을 통해 해당 노드를 방문했는지 관리합니다.

4. info[node]가 0이면 양의 cnt++, 1이면 늑대의 cnt++합니다.

• 늑대의 cnt가 양의 cnt와 같거나 크면 return
• 양의 cnt를 갱신하면서 maxSheep를 최종적으로 return

5. for-each문 사용해서 그래프에서 노드를 꺼냅니다. 없으면 새 ArrayList를 만듭니다.

• 방문을 안 했다면, 방문 표시를 하고 dfs를 돌립니다. 그리고 다음에 해당 노드의 새로운 루트를 확인해 볼 수 있도록 방문 false 처리를 합니다. (백트래킹)

6. 방문한 노드 중에서 추가적인 자식노드의 루트를 백트래킹을 사용해서 새로운 양을 찾습니다. (백트래킹)

 

코드 구현

1. 런타임 에러

import java.util.*;
class Solution {
    public int maxSheep = 0;

    public int solution(int[] info, int[][] edges) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int[] edge : edges) {
            graph.putIfAbsent(edge[0], new ArrayList<>());
            graph.get(edge[0]).add(edge[1]);
        }

        List<Integer> visited = new ArrayList<>();
        visited.add(0);
        dfs(0, 0, 0, visited, graph, info);

        return maxSheep;
    }

    private void dfs(int node, int sheepCount, int wolfCount, List<Integer> visited,
                     Map<Integer, List<Integer>> graph, int[] info) {
        if (info[node] == 0) sheepCount++;
        else wolfCount++;

        if (wolfCount >= sheepCount) return;

        maxSheep = Math.max(maxSheep, sheepCount);

        for (int next : graph.getOrDefault(node, new ArrayList<>())) {
            if (!visited.contains(next)) {
                visited.add(next);
                dfs(next, sheepCount, wolfCount, visited, graph, info);
                visited.remove(next);
            }
        }

        for (int i = 0; i < info.length; i++) {
            if (visited.contains(i) && graph.containsKey(i)) {
                for (int next : graph.get(i)) {
                    if (!visited.contains(next)) {
                        visited.add(next);
                        dfs(next, sheepCount, wolfCount, visited, graph, info);
                        visited.remove(next);
                    }
                }
            }
        }
    }
}

에러내용:

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index 10 out of bounds for length 10

 

문제의 원인:

 remove 메서드 사용: visited.remove(next)는 next 값을 가진 요소를 리스트에서 제거합니다. 이는 next가 값으로 해석되며, IndexOutOfBoundsException 오류를 일으킬 수 있습니다.

또한 List를 사용해서 방문관리를 하면 contains, add, remove 연산에서 시간 복잡도가 O(n)인데, boolean[] 사용 시 각 노드의 방문 여부를 O(1)로 알 수 있습니다.

 

 

2. 성공 코드 - List<Integer> 대신 boolean[] 배열을 사용하여 방문 여부를 추적

각 노드의 인덱스를 배열의 인덱스로 사용하고, 방문했을 경우 해당 인덱스의 값을 true로 설정합니다.

import java.util.*; 

class Solution {
    public int maxSheep = 0;

    public int solution(int[] info, int[][] edges) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int[] edge : edges) {
            graph.putIfAbsent(edge[0], new ArrayList<>());
            graph.get(edge[0]).add(edge[1]);
        }

        boolean[] visited = new boolean[info.length];
        visited[0] = true;
        dfs(0, 0, 0, visited, graph, info);

        return maxSheep;
    }

    private void dfs(int node, int sheepCount, int wolfCount, boolean[] visited,
                     Map<Integer, List<Integer>> graph, int[] info) {
        if (info[node] == 0) sheepCount++;
        else wolfCount++;

        if (wolfCount >= sheepCount) return;

        maxSheep = Math.max(maxSheep, sheepCount);

        for (int next : graph.getOrDefault(node, new ArrayList<>())) {
            if (!visited[next]) {
                visited[next] = true;
                dfs(next, sheepCount, wolfCount, visited, graph, info);
                visited[next] = false;
            }
        }
         for (int i = 0; i < info.length; i++) {
            if (visited[i] && graph.containsKey(i)) {
                for (int next : graph.get(i)) {
                    if (!visited[next]) {
                        visited[next] = true;
                        dfs(next, sheepCount, wolfCount, visited, graph, info);
                        visited[next] = false;
                    }
                }
            }
        }
    }
}

 

배우게 된 점

1. Map에서 getOrDefault 메서드를 사용할 때, 주어진 키에 해당하는 값이 맵에 존재하지 않으면, 지정된 기본값을 반환하는 방식으로 작동합니다.

List<Integer> children = tree.getOrDefault(node, new ArrayList<>());

여기서 node는 tree 맵에서 찾고자 하는 키입니다.

• 만약 tree 맵에 node라는 키가 존재한다면, 해당 키에 대응하는 List<Integer> 타입의 값을 반환합니다.
• 만약 tree 맵에 node라는 키가 존재하지 않는다면, new ArrayList<>()와 같이 새로운 ArrayList<Integer> 인스턴스를 기본값으로 반환합니다.

이 방식은 맵에서 키에 해당하는 값이 없을 때 null을 반환하는 대신, 기본적으로 사용할 수 있는 빈 리스트를 제공하여 NullPointerException과 같은 오류를 방지할 수 있도록 해줍니다.

 

반면, Collections.emptyList()

List<Integer> children = tree.getOrDefault(node, Collections.emptyList());

Collections.emptyList()는 불변의 특성이 있는 빈 리스트를 반환합니다. 즉, 이 리스트에 새로운 요소를 추가하거나 기존 요소를 삭제할 수 없습니다. 시도하면 UnsupportedOperationException 오류가 발생합니다. 매번 새로운 객체를 생성하지 않고 동일한 빈 리스트 객체를 반환하므로 빈 리스트가 필요할 때 매번 새로운 ArrayList 객체를 생성하는 것보다 메모리 사용을 줄여줍니다.

 

따라서, 반환된 리스트에 새로운 요소를 추가할 계획이 없다면 Collections.emptyList()를 사용하는 것이 좋으며, 추후에 요소를 추가할 필요가 있다면 new ArrayList<>()를 사용하는 것이 적합합니다.

 

2. 주어진 배열을 통해  인접리스트 만들기

Map<Integer, List<Integer>> graph = new HashMap<>();

for (int[] edge : edgeSet) {
    graph.putIfAbsent(edge[0], new ArrayList<>());
    graph.get(edge[0]).add(edge[1]);
}

 

3. visited.remove(next);의 역할

백트래킹 구현의 중 언제 그리고 왜  .remove(node)를 해주어야 하는지 판단하는 것은 중요합니다. 

visited.add(next_node);
dfs(next_node, sheepCount, wolfCount, visited, graph, info);
visited.remove(next);

1. visited.add(next_node);
   탐색 중에는 visited 리스트에 현재 방문한 노드를 추가합니다.
2. dfs(next_node, sheepCount, wolfCount, visited, graph, info);
   해당 노드의 모든 자식 노드에 대한 탐색을 시작합니다.
3. visited.remove(next_node);
   2번이 끝나면, visited 리스트에서 해당 노드를 제거함으로써 next_node 노드를 방문하기 이전의 상태로 되돌아갑니다.

WHY?

이는 다른 경로에서 next_node 노드를 새로운 가능성으로 고려할 수 있도록 해줍니다.
백트래킹 없이 visited 리스트에서 노드를 제거하지 않으면, 한 번 방문한 노드는 다시 방문할 수 없게 되는데 이는 그래프의 모든 가능한 경로를 탐색하는 데 제한을 두게 됩니다.

 

4. 이미 방문한 노드 && 추가적인 자식노드가 있는지 백트래킹을 통해 확인

if (visited.contains(i) && graph.containsKey(i)){
  // 현재 노드(i)의 자식 노드(next)들을 순회
	for (int next : graph.get(i)) {
      // 아직 방문하지 않은 자식 노드만을 대상
      if (!visited.contains(next)) {
          visited.add(next);
          dfs(next, sheepCount, wolfCount, visited, graph, info);
          visited.remove(next);
      }
    }
}