[백준 2522번][Java] 사회망 서비스 - 트리, DP, 메모이제이션

www.acmicpc.net/problem/2533

2533번: 사회망 서비스(SNS)

 

문제 풀이

 

얼리 어답터(EA)를 이용해 모든 아이디어를 퍼트리기 위해서는 다음의 규칙이 필요합니다.

 

1. 현재 노드가 EA인 경우

- 자식 노드가 EA인 경우

- 자식 노드가 EA가 아닌 경우



2. 현재 노드가 EA가 아닌 경우

- 모든 자식 노드가 EA여야 한다.

 

위의 규칙을 적용해 트리 구조에서 재귀를 이용해 해결할 수 있습니다.

재귀를 이용해 구현할 때, 리프노드에서의 종결 조건과 맞물려서 최소값을 구하려면 약간 껄끄러운 면이 있습니다.

리프노드에서 0을 반환해야 하는 경우엔 모든 값이 0이 되어버리기 때문입니다.

그래서 반대로 얼리어답터가 아닌 노드의 최대값 문제로 변환해서 풀었습니다.

 

참고) 이 문제에는 루트 정점이 특별이 지정되지 않았지만 사이클이 없는 트리 구조 특성상 어느 정점을 선택하든지 

답을 찾을 수 있습니다.

 

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

import static java.lang.Math.max;

public class Main {
	static int N;
	static int[][] cache;
	static boolean[] visited;
	static List<List<Integer>> adj;
	public static void main(String[] args) throws IOException {
//		InputReader reader = new InputReader("testcase.txt");
		InputReader reader = new InputReader();
		N = reader.readInt();
		adj = new ArrayList<>();
		cache = new int[N+1][2];
		for (int i = 0; i <= N; i++) {
			Arrays.fill(cache[i], -1);
		}
		for (int i = 0; i <= N; i++) { adj.add(new ArrayList<>());}

		for (int i = 0; i < N-1; i++) {
			StringTokenizer st = new StringTokenizer(reader.readLine());
			int u = Integer.parseInt(st.nextToken()); int v = Integer.parseInt(st.nextToken());
			adj.get(u).add(v);
			adj.get(v).add(u);
		}
		visited = new boolean[N+1];
		int a = solve(1, true);
		int b = solve(1, false);
//		System.out.println(a + " " +b);
		int ret = max(a,b);
		System.out.println(N-ret);
	}

	private static int solve(int node, boolean isEarlyAdaptor) {
		int isEarlyAdaptorVal = isEarlyAdaptor ? 1 : 0;
		if(cache[node][isEarlyAdaptorVal] != -1) return cache[node][isEarlyAdaptorVal];

		visited[node] = true;

		int ret = isEarlyAdaptor ? 0 : 1;
		for (int i = 0; i < adj.get(node).size(); i++) {
			int childNode = adj.get(node).get(i);
			if(visited[childNode]) continue;
			//현재 노드가 ea라면 자식노드는 ea가 아닐 수도 있다.
			if(isEarlyAdaptor) {
				ret += max(solve(childNode, false),
						solve(childNode, true));
				continue;
			}
			//현재 노드가 ea가 아니라면 모든 자식 노드는 ea여야 한다.
			ret += solve(childNode, true);
		}
		visited[node] = false;
//		return ret;
		return cache[node][isEarlyAdaptorVal] = ret;
	}
}
class InputReader {
	private BufferedReader br;

	public InputReader() {
		br = new BufferedReader(new InputStreamReader(System.in));
	}

	public InputReader(String filepath) {
		try {
			br = new BufferedReader(new FileReader(filepath));
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
	}

	public List<Character> readLineIntoCharList() throws IOException {
		List<Character> l = new ArrayList<>();
		while(true) {
			int readVal = br.read();
			if(readVal == '\n' || readVal == -1) break;
			l.add((char)readVal);
		}
		return l;
	}

	public boolean ready() throws IOException {
		return br.ready();
	}

	public String readLine() throws IOException {
		return br.readLine();
	}
	public int readInt() throws IOException {
		return Integer.parseInt(readLine());
	}
	public Long readLong() throws IOException {
		return Long.parseLong(readLine());
	}
}