[백준] 5021번: 왕위 계승

문제

백준 - 5021번: 왕위 계승

분석

유토피아를 세운 사람의 이름과 가족 정보가 주어지고, 왕위를 계승받기를 주장하는 사람의 이름이 주어질 때 가장 나라를 세운 사람과 혈통이 가까운 사람을 구하는 문제이다.

왕위를 주장하는 사람의 혈통을 구하기 위해DFS를 이용한다.
유토피아를 세운 사람이면 1을 가져오고 부모가 없는 경우는 0을 가져온다.
두 부모의 혈통을 더하고 반으로 나눈 값이 본인의 혈통 값이므로 dfs가 리턴되면서 값이 채워진다. 그리고 중복해서 계산하지 않기 위해 한 번 계산한 값은 map에 저장해두고 사용할 일이 있다면 바로 가져다 쓴다.

N과 M만큼의 for문이 있고 dfs에서는 메모이제이션을 사용했기 때문에 O(N+M)이 시간 복잡도이다.

코드

해결언어 : Java

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class Main {
	static int N, M;
	static Map<String, String[]> parent;
	static Map<String, Double> blood;
	static String first;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		parent = new HashMap<>();
		blood = new HashMap<>();
		first = br.readLine();
		blood.put(first, 1.0);
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			String c = st.nextToken();
			String p1 = st.nextToken();
			String p2 = st.nextToken();
			parent.put(c, new String[] { p1, p2 });
		}
		String ans = "";
		double mx = 0;
		for (int i = 0; i < M; i++) {
			String name = br.readLine();
			double b = getBlood(name);
			if (b > mx) {
				mx = b;
				ans = name;
			}
		}
		System.out.println(ans);
		br.close();
	}

	static double getBlood(String name) {
		if (blood.containsKey(name))
			return blood.get(name);
		if (name.equals(first))
			return 1;
		if (!parent.containsKey(name))
			return 0;
		String[] p = parent.get(name);
		blood.put(name, (getBlood(p[0]) + getBlood(p[1])) / 2);
		return blood.get(name);
	}
}