[JAVA]사회망 서비스(SNS)(BOJ-2553 [그래프])

📂문제 설명

 

페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망에서 사람들의 친구 관계는 그래프로 표현할 수 있는데,  이 그래프에서 사람은 정점으로 표현되고, 두 정점을 잇는 에지는 두 정점으로 표현되는 두 사람이 서로 친구 관계임을 표현한다. 

예를 들어, 철수와 영희, 철수와 만수, 영희와 순희가 서로 친구 관계라면 이를 표현하는 친구 관계 그래프는 다음과 같다. 

친구 관계 그래프를 이용하면 사회망 서비스에서 어떤 새로운 아이디어가 전파되는 과정을 이해하는데 도움을 줄 수 있다. 어떤 새로운 아이디어를 먼저 받아들인 사람을 얼리 아답터(early adaptor)라고 하는데, 사회망 서비스에 속한 사람들은 얼리 아답터이거나 얼리 아답터가 아니다. 얼리 아답터가 아닌 사람들은 자신의 모든 친구들이 얼리 아답터일 때만 이 아이디어를 받아들인다. 

어떤 아이디어를 사회망 서비스에서 퍼뜨리고자 할 때, 가능한 한 최소의 수의 얼리 아답터를 확보하여 모든 사람이 이 아이디어를 받아들이게 하는  문제는 매우 중요하다. 

일반적인 그래프에서 이 문제를 푸는 것이 매우 어렵다는 것이 알려져 있기 때문에, 친구 관계 그래프가 트리인 경우, 즉 모든 두 정점 사이에 이들을 잇는 경로가 존재하면서 사이클이 존재하지 않는 경우만 고려한다. 

예를 들어, 8명의 사람으로 이루어진 다음 친구 관계 트리를 생각해보자. 2, 3, 4번 노드가 표현하는 사람들이 얼리 아답터라면, 얼리 아답터가 아닌 사람들은 자신의 모든 친구가 얼리 아답터이기 때문에 새로운 아이디어를 받아들인다.

친구 관계 트리가 주어졌을 때, 모든 개인이 새로운 아이디어를 수용하기 위하여 필요한 최소 얼리 어답터의 수를 구하는 프로그램을 작성하시오.

 

입력

첫 번째 줄에는 친구 관계 트리의 정점 개수 N이 주어진다. 단, 2 <= N <= 1,000,000이며, 각 정점은 1부터 N까지 일련번호로 표현된다. 두 번째 줄부터 N-1개의 줄에는 각 줄마다 친구 관계 트리의 에지 (u, v)를 나타내는 두 정수 u 와 v가 하나의 빈칸을 사이에 두고 주어진다. 

 

출력

주어진 친구 관계 그래프에서 아이디어를 전파하는데 필요한 얼리 아답터의 최소 수를 하나의 정수로 출력한다.

 

---

📂아이디어 및 알고리즘(문제풀이)

• 문제 접근
  • 자신과 근접한 친구들과는 둘 중 한명이 얼리아답터여야 하고 N명에서 최소한의 얼리어답터 인원수를 구하면 되는 문제이다. 
  • 문제에서는 시간제한이 3초인것을 보면 N^2이면 시가 초과이기 때문에 이 점을 유의해서 풀어야 한다.
  • DFS를 이용해 N개의 노드를 한번씩만 방문해서 최소한의 얼리아답터를 구하기 위해서는
  • DP개념을 이용하여 "얼리어답터인 경우와 아닌 경우"를 나눠서 다음 노드를 방문할때마다 결과 값을 저장해 가며 찾아주도록 한다.
  • 가장 중요한건 나랑 근접한 친구도 얼리어답터가 가능하다. 즉 꼭 둘 중 한명만 얼리아답터이지 않는다!!
• 문제 풀이
  • 입력 받은 값 들을 이용하여 먼저 해당 노드마다의 간선 정보를 추가해준다. Arraylist<Arraylist<Integer>> list
  • DFS에 들어가는 parameter값에는 { 현재 index값, 방문 visited, 얼리아답터 정보 check } 값 들을 저장해갈 DP를 넣어준다.
  • 여기서 DP[index][0]은 얼리어답터가 아닌 경우, DP[index][1]은 얼리어답터일 경우를 의미한다.
  • DFS안에는 index로 방문 여부를 true로 정하고 DP정보에 대한 초기값을 입력해준다.
    • for문에서는 해당 index에서 연결된 노드를 순회하게하여 next index로 DFS를 연결해준다.
    • DP값들을 더해주는거 보다 먼저 DFS로 가는 이유는 DP값에 대한 초기값을 설정해 주기 위해서다.
    • 그렇게 하면 DP값을 더하기 전 초기값들을 전부 정할 수 있게 되고 마지막 노드에 해당하는 값부터 시작하여 얼리어답터인 경우와 아닌경우를 더해가며 최솟값을 찾아준다.
    • DP[index][0]에는 index가 얼리어답터가 아닌경우 이므로 그와 연결된 DP[next index][1]값을 넣어준다.
    • DP[index][1]에는 index가 얼리어답터인 경우 그와 연결된 DP[next index][0], DP[next index][1] 둘 중 작은 값을 넣어준다. [얼리어답터도 얼리어답터 친구를 가질 수 있다.]
  • 최종적으로 DFS의 시작인 index=1인 값에 대한 DP값중 최솟값을 출력해주면 된다.
  • return Math.min(DP[1][0], DP[1][0]); 

 

📂소스 코드

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	
	 public static int Solution(ArrayList<ArrayList<Integer>> list, int n) {
	        
		 int dp[][] = new int[n+1][2];
		 boolean check[] = new boolean[n+1];
		 boolean visited[] = new boolean[n+1];
	
		 DFS(1, list, n, check, visited,dp);
		 return Math.min(dp[1][0], dp[1][1]);
	 }

	public static void DFS(int index, ArrayList<ArrayList<Integer>> list, int n, boolean[] check, boolean[] visited, int [][]dp) {
		
		visited[index] = true; //방문 여부
		dp[index][0] = 0; //얼리어답터가 아닌 경우
		dp[index][1] = 1; //얼리어답터인 경우
		
		ArrayList<Integer> test = list.get(index);
		
		for(int next : test) {
			if(visited[next] != true) {
				DFS(next, list, n, check, visited,dp);
				dp[index][0] += dp[next][1];
				dp[index][1] += Math.min(dp[next][0],dp[next][1]);
			}
		}
	
	}
	 
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
		
		for(int i=0;i<=n;i++) {
			list.add(new ArrayList<Integer>());
		}
		for(int i=0;i<n-1;i++) {
			int x = sc.nextInt();
			int y = sc.nextInt();
			list.get(x).add(y);
			list.get(y).add(x);
		}
		int result = Solution(list, n);
		System.out.println(result);
	}
}

 

 

📂출처

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

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