1135 뉴스 전하기 [JAVA]
문제분석
https://www.acmicpc.net/problem/1135
트리 구조로 이루어진 직원 간 관계 (상사-부하, 1:n)가 주어지고 루트 노드에서부터 자신의 부하 중 1명에게 전화를 순차적으로 해갈 때 모든 노드가 전화를 받게 되는 최소의 시간을 구하는 것이 목표인 문제다.
처음 문제를 보고 풀 떈 boss와 subList를 가지는 Member객체를 만들고 부하 직원 추가 시 그 위 객체(boss)들의 총 sub의 수를 갱신시켜주는 방식으로 구현하고
각 member의 subList를 이 총 sub의 count를 기준으로 PQ로 다시 만들어준 후
탐색 시 bfs로 돌면서 sub PQ를 poll해가며 1초씩 진행하는 방식으로 구현했었다.
그런데... 문제는 틀렸다고 나왔고, 이유를 전혀 모르겠었다.
https://www.acmicpc.net/board/view/760
위 질문게시판을 보고 딱 알게 되었다.
input이
23
-1 0 1 1 1 2 2 2 3 3 3 4 4 4 0 14 15 16 17 18 19 20 21
이렇게 들어온다면 ?
0번 노드의 자식(0,14) 중, 자식의 수는 왼쪽 idx 1번 노드가 많지만, 실제 탐색은 14번 노드로 가는 길이 더 오래걸리게 된다.
즉, 단순히 자식의 수를 가지고 탐색의 우선순위를 정할 수 없게 된다. (스스로 그림을 그려보길 바란다.)
따라서, 다른 기준점을 가지고 이 문제를 해결해야 한다.
고민을 하다 든 생각이 노드의 최선으로 가지만 최악의 시간을 구해보는 것이다.
내가 생각해낸 방법은 다음과 같다.
어디 내놓기 정말 부끄러운 그림이지만..
파란색을 해당 노드 자식의 최악 순서
주황색을 해당 노드의 부모의 입장에서 그리디한 선택을 하는 경우 최악의 순서(시간)
이라고 보면 된다.
왼쪽 하단 자식이 2개의 리프노드로 구성된 노드 X 를 보자.
두 리프 노드 모두 자식이 없기에 자식의 최악 순서는 0이 된다. (파란색)
두 리프 노드의 부모 노드 X 입장에선 자신의 자식들이 모두 같은 최악 순서 값을 가지니 그 어떤걸 선택해도 되는 상태가 된다.
따라서, 두 리프 노드의 최악의 순서값은 2가 된다 (주황색)
다음으로 올라가서, 그 오른쪽의 리프 노드와 방금 전 노드 X를 비교해보자.
X의 subWorst (자식 중 최악의 경우 걸리는 시간의 max값)는 2가 되고 (파란색)
그 옆의 노드의 경우 리프노드이기에 0이 된다.
따라서, X의 부모 노드의 입장에선 더 오래 걸리는게 확실한 X에게 먼저 전화를 걸어야 한다 (그리디)
그러므로, X의 최악 순서값은 1이되고 그 옆의 최악 순서값은 2가 된다 (주황색)
마찬가지의 방식으로 쭉 순서를 정리해보면 루트 노드 기준 두 자식의 worst는 7로 동일하므로 그 어떤 선택을 해도 최소 9초가 걸리게 된다. (왼쪽 노드를 먼저 탐색하면 왼쪽 노드 탐색에 8초(1+7) 오른쪽 노드를 탐색하는 동안 총 9초 (2+7) / 반대의 경우 왼쪽 9초 오른쪽 8초가 되기 때문)
코드
import java.util.*;
import java.util.stream.Collectors;
public class Main {
static Member[] members;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
members= new Member[n];
for (int i = 0; i < n; i++) {
members[i] = new Member(i);
}
sc.nextInt();
for (int i = 1; i < n; i++) {
int bossIdx = sc.nextInt();
members[i].boss = members[bossIdx];
members[bossIdx].directSubList.add(members[i]);
}
update(members[0]);
System.out.println(members[0].subWorst);
}
static class Member{
int idx;
Member boss;
List<Member> directSubList;
int subWorst;
int totalWorst;
public Member(int idx){
directSubList = new ArrayList<>();
subWorst = -1;
totalWorst = 0;
this.idx = idx;
}
}
static void update(Member member){
if(!member.directSubList.isEmpty()){
for (Member sub : member.directSubList) {
update(sub);
}
}
// subWorst는 이미 제대로 구해져있다.
member.directSubList.sort(((o1, o2) -> o2.subWorst - o1.subWorst));
int maxSubTotalWorst = 0;
//rank
Set<Member> dupMemberSet = new HashSet<>();
int bef = -1;
for (int i = 0; i < member.directSubList.size(); i++) {
Member subMember = member.directSubList.get(i);
if(bef == subMember.subWorst)
dupMemberSet.add(subMember);
else if(!dupMemberSet.isEmpty()){
for (Member dupMem : dupMemberSet) {
dupMem.totalWorst = dupMem.subWorst+i;
maxSubTotalWorst = Math.max(maxSubTotalWorst, dupMem.totalWorst);
}
dupMemberSet.clear();
}else{
dupMemberSet.add(subMember);
}
bef = subMember.subWorst;
}
for (Member dupMem : dupMemberSet) {
dupMem.totalWorst = dupMem.subWorst+member.directSubList.size();
maxSubTotalWorst = Math.max(maxSubTotalWorst, dupMem.totalWorst);
}
dupMemberSet.clear();
member.subWorst = maxSubTotalWorst;
}
}
update 메소드만 간단하게 살펴보면
대상 member (초기값으로 루트노드가 들어오게 된다)의 자식들의 subWorst를 구하고
이걸 바탕으로 자식들의 totalWorst를 그리디하게 계산하여
자신의 subWorst를 구하는 로직이다.
dumMemberSet을 정의한 곳 부터 member.subWorst를 저장하는 곳 직전까지의 코드가 좀 지저분하긴 한데
해당 로직은 member의 직속부하들의 subWorst값을 기준으로 정렬하여 동일한 경우 같은 우선순위를 부여하기 위한 코드이다.
쉽게 생각하면 6명이서 달리기 시합하는데 1등 공동 3등 2명, 공동 6등 3명 이렇게 등수를 매겨주기 위한 것이다.
해당 등수를 매겨 총 worst값을 구하고 이걸 바탕으로 member의 subWorst값을 구할 수 있게 된다.