문제 링크
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 함수를 완성해주세요.
제한사항
알고리즘: DFS, 비트마스킹
풀이
최대한 많은 수의 양을 탐색하는 게 목표이다.
탐색이 가능한 순서라면 (양의 수가 더 많음) 탐색한 노드들을 하나의 집합으로 비트 마스킹해서 방문 처리를 해준다. 예를 들면 1 -> 2 -> 3 ->4가 탐색이 가능한 순서라면 1 -> 3 -> 4 ->2나
1 -> 4 -> 2 -> 3이나 똑같은 탐색이기 때문에 중복 처리를 해준다. 이렇게 중복 처리하면서 모든 탐색 노드 집합을 살펴보면 최대한으로 얻을 수 있는 양의 수를 구할 수 있다.
경우의 수는 2^17이기 때문에 가능한 풀이다.
여기서 탐색이 가능한 집합은 DFS을 이용해서 구한다.
예를 들어) 0에서는 1, 8로 갈 수 있다. 0에서 1로 탐색한다면,
1에서는 2, 4, 8 탐색 할 수 있다. ->(8로 갈 수 있는 이유 1 -> 0 -> 8) 1에서 4로 탐색한다면,
4에서는 3, 6, 2, 8 탐색 할 수 있다.
...
이런 식으로 탐색할 수 있는 집합을 찾고, 중복 처리를 해주면서 탐색할 노드가 없거나, 양의 수와 늑대 수가 같아질 때 양의 수를 max로 업데이트 해주면 된다.
소스 코드
import java.util.*;
class Node {
int sheep, wolf;
Node(int sheep, int wolf) {
this.sheep = sheep;
this.wolf = wolf;
}
}
class Solution {
static boolean[] visited = new boolean[(int)Math.pow(2, 17) + 1];
static ArrayList<Integer>[] tree;
static int answer = -1;
public int solution(int[] info, int[][] edges) {
tree = new ArrayList[info.length];
for(int i=0; i<tree.length; i++) tree[i] = new ArrayList<>();
for(int i=0; i<edges.length; i++) tree[edges[i][0]].add(edges[i][1]);
ArrayList<Integer> node_list = new ArrayList<>();
node_list.add(0);
visited[1] = true;
DFS(node_list, 1, 0, new Node(1,0), info);
return answer;
}
static void DFS(ArrayList<Integer> node_list, int set, int cur_n, Node info_n, int[] info) {
for(int i=0; i<tree[cur_n].size(); i++) node_list.add(tree[cur_n].get(i)); //자식 노드 추가
node_list.remove(Integer.valueOf(cur_n)); //현재 노드 삭제
if((info_n.sheep == info_n.wolf) || (node_list.size() == 0)) {
//더이상 갈 수 없거나, 다음 탐색 노드가 없는 경우 업데이트
answer = Math.max(answer, info_n.sheep);
return;
}
for(int i=0; i<node_list.size(); i++) {
int b = node_list.get(i);
int next_set = set | (1 << b);
if(!visited[next_set]) {
visited[next_set] = true;
Node next_info = new Node(info_n.sheep, info_n.wolf);
ArrayList<Integer> copy_node_list = deep_copy(node_list);
if(info[b] == 0) next_info.sheep += 1;
else next_info.wolf += 1;
DFS(copy_node_list, next_set, b, next_info, info);
}
}
}
static ArrayList<Integer> deep_copy(ArrayList<Integer> list) {
ArrayList<Integer> node_list = new ArrayList<>();
node_list.addAll(list);
return node_list;
}
}