[BOJ2533/Java] 사회망 서비스(SNS)

문제 요약

https://www.acmicpc.net/problem/2533

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

먼저 말씀드립니다.. 문제를 봐도 완탐형태밖에 생각이 안나는데

N이 너무 커서 어떻게 완탐을 하게 된다면 안될 거라는 생각을 했고

근데 이걸 어떻게 다르게 풀어야할지 모르겠어서 구글링을 했습니다..

 

문제 요약은 다음과 같음

 

친구관계 트리에서 새로운 아이디어를 받아들이기 위한 최소한의 얼리어답터수를 구하려고 하는데

새로운 아이디어를 받아들이기 위해서는 한 사람의 친구가 모두 얼리어답터여야 한다.

문제에서 주는 트리 구조는 매우 단순하다는 것이 그나마 다행스러운 점이었다.

 

입/출력

아까 얘기한대로 N이 좀 크다.. 비효율적인 탐색시 바로 시간 초과가 날것..이 뻔했다..

 

접근 방식

완전탐색에서는  1~n까지의 사람들이 각각 얼리어답터인지 아닌지를 확인하고 또 그렇게 됐을 때 모두가 아이디어를 받아들이는지 확인해야 한다.

이걸 어떻게 dp로 바꿔서 단순화할 수 있을까?

일단 dp배열에는 각 경우에 최소 몇명이 얼리어답터여야 하는지를 저장하는 것으로 두자.

그리고 한 사람(a)이 얼리어답터인 경우(dp[a][0])와 얼리어답터가 아닌 경우(dp[a][1])를 생각해볼 때

a가 얼리어답터라면 a와 이어진 친구(자식들)은 얼리어답터여도 되고 아니여도 된다.

즉, a의 자식들에 대해서 얼리어답터인 경우와 아닌경우를 달리하여 구한 뒤 그 중 최소값을 dp[a][0]에 더한다.

a가 얼리어덥터가 아니라면 a의 자식들은 무조건 얼리어답터여야 한다.

그래서 자식이 얼리어답터인 경우만 dp[a][1]에 값을 더하는 방식으로 진행한다.

이렇게 정리를 하면 자식 노드에 대해서 다시 탐색을 진행하면서 top-down 방식으로 dp 배열을 완성할 수 있다.

 

구현코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	
	static int n, parent;
	static ArrayList<ArrayList<Integer>> edge = new ArrayList<>();
	static int[][] dp;
	static boolean[] visited;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		n = Integer.parseInt(br.readLine());
		for(int i = 0; i<n; i++) {
			edge.add(new ArrayList<>());
		}
		dp = new int[n][2];
		visited = new boolean[n];
		for(int i = 0; i< n-1; i++) {
			st= new StringTokenizer(br.readLine());
			int v = Integer.parseInt(st.nextToken())-1;
			int w = Integer.parseInt(st.nextToken())-1;
			edge.get(v).add(w);
			edge.get(w).add(v);
		}
		find(0);
		System.out.println(Math.min(dp[0][0], dp[0][1]));
	}
	
	static void find(int s) {
		visited[s] = true;
		dp[s][0] = 1;
		for (int w : edge.get(s)) {
			if(visited[w]) continue;
			find(w);
			dp[s][1] += dp[w][0];
			dp[s][0] += Math.min(dp[w][1], dp[w][0]);
		}
	}

}

추가로 첨언하자면 arraylist 말고 node를 따로 만들어서 엣지에 대한 접근을 좀 더 부드럽게 만들면 시간이 더 많이 줄어드는 것 같았다..