[2022 KAKAO BLIND RECRUITMENT] 양과 늑대

[uijin-j]

🔗 양과 늑대

[uijin-j]

📑 댓글 템플릿

• Language : Java
• 성능

코드 풀이

```java import java.util.*; // 18:55 START! 20:41 END! (약 2시간..) // PQ를 2개 쓰는 문제! class Solution { /** * 이분탐색? X * 그리디? 항상 가장 가까운 양(만약 양이 없으면 가장 양과 가까운 늑대)을 데려가다가, 갈 수 없으면 그대로 끝! * 1. 모든 늑대 노드에서 가장 가까운 양까지 거리 구하기 (아래 방향으로만) * 2. 루트 노드부터 bfs with 우선순위 큐 * * ❗️ 그런데, 단순히 가장 가까운 양으로 하면 안됨! 다음 양이 현재 갈 수 있는 거리 내에 있으면 하위에 양이 더 많은 쪽으로 가는 것이 더 이득! */ public class Node { int num; int type; // 양은 0, 늑대는 1 int distToSheep; // 가장 가까운 양까지의 거리 int numOfSheep; // 하위에 있는 양의 수 public Node(int num, int type, int dist, int numOfSheep) { this.num = num; this.type = type; this.distToSheep = dist; this.numOfSheep = numOfSheep; } } public int solution(int[] info, int[][] edges) { int n = info.length; List> tree = new ArrayList<>(); for(int i = 0; i < n; ++i) tree.add(new ArrayList<>()); for(int[] edge : edges) tree.get(edge[0]).add(edge[1]); Map map = new HashMap<>(); for(int i = 0; i < n; ++i) { int type = info[i]; int[] distAndCount = calculateDistAndCount(i, tree, info); map.put(i, new Node(i, type, distAndCount[0], distAndCount[1])); } PriorityQueue pq = new PriorityQueue<>((a, b) -> a.distToSheep - b.distToSheep); pq.offer(map.get(0)); int sheep = 0; int wolf = 0; while(!pq.isEmpty()) { int possible = Math.max(0, sheep - 1 - wolf); PriorityQueue pq2 = new PriorityQueue<>((a, b) -> b.numOfSheep - a.numOfSheep); while(!pq.isEmpty() && pq.peek().distToSheep <= possible) { pq2.offer(pq.poll()); } if(pq2.isEmpty()) break; Node node = pq2.poll(); while(!pq2.isEmpty()) { pq.offer(pq2.poll()); } if(node.type == 0) sheep += 1; else wolf += 1; for(int next : tree.get(node.num)) { pq.offer(map.get(next)); } } return sheep; } // bfs! public int[] calculateDistAndCount(int start, List> tree, int[] info) { Queue q = new LinkedList<>(); q.offer(start); int min = Integer.MAX_VALUE; int count = 0; if(info[start] == 0) { min = 0; count = 1; } int dist = 1; while(!q.isEmpty()) { int size = q.size(); for(int i = 0; i < size; ++i) { int node = q.poll(); for(int next : tree.get(node)) { if(info[next] == 0) { min = Math.min(min, dist); count++; }; q.offer(next); } } dist++; } return new int[]{min, count}; } } ```

코멘트

- 역시나 쉽지 않은 문제였습니다.. 힌트보고 풀었네요..

[hye-on]

• Language : C++
• 성능

코드 풀이

```cpp #include #include #include #include using namespace std; //08:52 //0은 양, 1은 늑대 // visit처리 땜에 dfs //양 쪽의 최대 양을 가져올 수 있는 개수 vectorlink[17]; bool visit[17]; int maxS; vector info; queuesq; void dfs(int node,int s, int w, queueq){ if(s<=w) return; if(s>maxS){ maxS = s; } for(int i=0;i _info, vector> edges) { int answer = 0; info = _info; for(int i=0;i

코멘트

- 정말.. 이런 생각을 어떻게 하죠 어려웠습니다.