[7주차_화요일] 왕위 계승

[KodaHye]

• 사이트 : 백준(BOJ)
• 문제: 왕위 계승
• 번호: 5021

### 🤔 시간복잡도 고려사항

### 💡 풀이 아이디어

[KodaHye]

🤔 시간복잡도 고려사항

• 2 <= N, M <= 50
• 사람들 간 연결 관계를 확인해야 하므로 그래프로 구현하면 좋을 것 같다는 생각을 함
• N: 주어지는 가족 정보의 수
• M: 왕위 계승을 주장하는 사람의 수
• 노드의 수: N, 간선의 수: 2 × N
• 사이클이 없는 방향 그래프이므로 위상정렬로 문제 풀이 가능
  • 시간 복잡도: O(N + 2N)

💡 풀이 아이디어

• 주어지는 가족 정보의 수가 N개이기 때문에 사람과 관련된 정보는 배열로 저장하는데, 크기를 3N(최대 가능 사람 수)으로 설정
• HashMap<String, Integer> nameToIdx: 이름을 idx로 바꿔주는 HashMap
• hashMap<Integer, String> idxToName: idx를 이름으로 바꿔주는 변수
• double[] score: 각 사람들의 혈통 점수를 저장하는 변수
• ArrayList<Integer>[] adj: 인접 리스트 저장
  • 이름을 입력받았을 때, idx로 변환하고, idx끼리 연결관계를 저장
• int[] degree: 진입차수 배열 저장
• boolean[] select: 왕위 계승을 주장하는 사람인지 저장
• solution()
  • 진입차수가 0일 때
  • 왕의 idx라면 혈통 점수를 1로 설정
  • 왕의 idx가 아니라면 혈통 점수를 0.5로 설정
  • while(!q.isEmpty())
  • 왕위 계승을 주장하는 사람이면서 혈통 점수가 크다면 왕위 계승을 받는 자식으로 설정
  • 진입차수의 값을 1씩 빼주면서 혈통 점수 update
  • 진입차수의 값이 0이라면 queue에 넣어주기

[Jewan1120]

🤔 시간복잡도 고려사항

• 2 ≤ N, M ≤ 50 → N x M = 2,500이지만 최적화 가능할 듯!

💡 풀이 아이디어

• 노드가 String으로 주어짐 → HashMap을 이용한 트리
• 부모와 자식의 관계가 주어지고, 부모의 정보로 인해 만들어지는 자식들의 정보를 묻는 문제 → 트리 DP라고 생각
• 따라서 각 자식들이 주어질 때마다 재귀적으로 부모의 혈통값를 메모이제이션 하면서 자식의 혈통값을 찾아줌

  private static double recursive(String person) {
  // 미리 계산된 값이 있다면 반환 -> 메모이제이션
  if (bloodMap.containsKey(person) && bloodMap.get(person) > 0) {
      return bloodMap.get(person);
  }
  if (!tree.containsKey(person)) {
      return 0;
  }
  String[] parents = tree.get(person);
  double parent1Blood = recursive(parents[0]) / 2.0;
  double parent2Blood = recursive(parents[1]) / 2.0;
  double personBlood = parent1Blood + parent2Blood;
  bloodMap.replace(person, personBlood); // 메모이제이션
  return personBlood;
  }

  처음에 혈통값 넘겨주는 거 잘못 적어서 와장창 틀렸네요🐹

위상 정렬 문제였군요...😿

[baexxbin]

🤔 시간복잡도 고려사항

• 2 ≤ N, M ≤ 50
• N: 가족 정보 입력처리
• M: 후보자 주장 계산
• O(N+M)

💡 풀이 아이디어

• 후보들의 부모 피를 바탕으로 혈통 계산하기
• 그러기 위해선 가족구성도 만들고, 이를 바탕으로 피 계산하기

1. 가족구성도 만들기 (입력)

   • family해시맵에 자식(키) 부모(값)으로 정보 넣기

2. 가족구성도를 바탕으로 혈통 계산(cal())

   • 재귀, 메모리제이션 활용
   • info: 사람 별 혈통 정보
   • info의 혈통 정보가 있다면 반환, 없다면 부모로부터 혈통정보 계산하기
   • 부모가 없다면(왕족X) 0 값으로 지정

3. 가장 혈통 가까운 후보자 찾기

   • 후보자 돌면서 가장 혈통 큰값 반환

저도 재귀로 풀었는데,, 위상정렬 문제이길래 위상정렬 버전으로도 도전해봤는데 자꾸 틀렸다고 하네요.....ㅠㅠ

[yeongleej]

🤔 시간복잡도 고려사항

• N, M ≤ 50
• 사람 수 : 최대 150
• 위상정렬 시간복잡도 : O(V+E) == O(150 + M)

💡 풀이 아이디어****

• fMap: 자식 리스트를 나타내는 해시맵
• indegree: 진입차수(= 부모수)를 나타내는 해시맵
• score: 혈통 점수를 나타내는 해시맵
• 위상정렬 활용
  • 진입차수가 0인 사람들을 큐에 삽입
  • 큐가 빌 때까지 연결된 자식을 탐색하며 진입차수 -1
  • 내 자식의 혈통 점수는 (원래값 + 내혈통점수*0.5)
  • 진입차수가 0이된 사람들 큐에 삽입 && 결과리스트에 삽입
• 위상정렬 후 결과리스트에서 계승 후보자를 찾아 점수가 가장 큰(=왕과 가장 먼) 후보자를 출력

String으로 입력되서 인덱스처리하는 거랑, 계승할 때 혈통 점수 무시해서 해멨습니다 ㅎㅎㅎㅎ

[yeahdy]

🤔 시간복잡도 고려사항

• 알고리즘: dfs + 위상정렬
• 시간복잡도: 위상정렬 알고리즘에서의 DFS는 각 정점과 간선을 한 번씩 방문하기 때문에 O(V+E) 로 O(150 + 50)

💡 풀이 아이디어

• 위상정렬 알고리즘을 사용한 이유?

  문제의 "다시 자식이 부모의 부모가 되는 경우도 없다. 또, 한 사람이 여러 명의 자식이 될 수 도 없다."

  • 위상정렬은 방향만 있고, 사이클이 없는 그래프 특징을 가지고 있음
  • 문제에서 부모와 자식간의 계층관계를 보면 부모 → 자식 방향이 있고, 부모 ← 자식 방향으로 사이클이 발생하지 않음
  • Map<String,ArrayList<String>> families = new HashMap<>() 하나의 자식에 부모가 속해있는 <자식,자식의부모 리스트> 형태

• dfs 의 역할?
  • 한번 탐색한 간선은 다시 방문하지 않도록 깊이 탐색후 결과를 바로 리턴
  • 어떤 자식의 부모(아빠,엄마) 마다 깊이 탐색을 통해 해당 자식의 혈통을 계산하기 위함
  • 깊이 탐색이 깊어질수록 2로 나누기 때문에 자식의 혈통이 옅어짐
  • Map<String,Double> bloodRatio = new HashMap<>() 자식의 혈통을 저장하는 곳으로 깊이탐색을 통해 계산되는 자식의 혈통이 갱신된다.

위상정렬 이라는걸 처음알았는데, 진짜 어렵네요!?😧

[icegosimperson]

🤔 시간복잡도 고려사항

• 시간 복잡도 : O(V+E)

💡 풀이 아이디어

• 혈통 최대값 설정 : final long INF = 1L << 52;
• Map<String, List> childMap = new HashMap<>(); // 부모 자식 관계 저장
• Map<String, Integer> parentCount = new HashMap<>(); // 자식의 부모 수 (위상 정렬용)
• 부모-자식 관계 저장 ArrayList

• 자식의 부모 수 증가

          parentCount.put(child, parentCount.getOrDefault(child, 0) + 2);
          parentCount.putIfAbsent(parent1, 0);
          parentCount.putIfAbsent(parent2, 0);
  
          blood.putIfAbsent(child, 0L);  // 자식의 초기 혈통 값은 0
          blood.putIfAbsent(parent1, 0L); // 부모의 혈통 초기화
          blood.putIfAbsent(parent2, 0L); // 부모의 혈통 초기화

• 부모가 없는 사람은 큐에 추가 `queue.add(person);
• 혈통 계산

  while (!queue.isEmpty()) {
          String current = queue.poll();
          if (childMap.containsKey(current)) {
              for (String child : childMap.get(current)) {
                  blood.put(child, blood.get(child) + blood.get(current) / 2);  // 부모로부터 혈통을 물려받음
                  parentCount.put(child, parentCount.get(child) - 1); // 부모수 -1
                  if (parentCount.get(child) == 0) {
                      queue.add(child); // 부모가 모두 계산된 자식은 큐에 추가
                  }
              }
          }
      }