[BOJ] 백준 2533 - 사회망 서비스(SNS) 풀이

1. 문제

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

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

2. 풀이

• DP + 트리 + DFS로 해결할 수 있는 문제.
• 그래프에 속한 사람은 얼리어답터일수도 있고 아닐 수도 있으며, 얼리어답터가 아닌 사람은 바로 인접한 노드 모두가 얼리어답터일때 아이디어를 받아드릴 수 있다.
• 이를 바탕으로 DP 식을 작성할 수 있다.

dp[i][j] = r
(0 <= i <= n , j = 0 or 1)
i노드가 얼리어답터이거나 얼리어답터가 아닐 때 최소 얼리어답터 수 = r

• 이 문제의 풀이 포인트는 루트 노드에서 출발하여 모든 노드를 DFS로 돌면서 얼리어답터일때와 얼리어답터가 아닐 때의 dp값을 초기 값으로 셋팅한 후 리턴하면서 최소 얼리어답터 노드수를 계산하는 것이다.
  
  
• 이를 로직으로 구성하면 아래와 같다.
  
  
• 입력으로 주어지는 정보를 이용하여 인접리스트를 구성한다.
• 그 후 루트 노드인 1번 노드에서 DFS를 실행한다.
  • DFS 함수를 방문하면 visited를 true 처리한다.
  • 그 후 DFS 함수의 파라미터로 주어진 노드가 얼리어답터일 때와 얼리어답터가 아닐 때 DP 값을 넣어준다.
    
    • idx가 DFS 함수의 파라미터로 주어진 노드일 때
      1. dp[idx][0] = 0 : idx 노드가 얼리어답터가 아닐 때는 얼리어답터 수를 0으로 한다.
      2. dp[idx][1] = 1 : idx 노드가 얼리어답터일 때는 얼리어답터 수를 1으로 한다.
  • 파라미터로 주어진 노드의 인접노드를 반복문을 돌면서 다음과 같은 로직을 처리한다.
    • 재귀로 함수를 돌면서 DP 값을 셋팅해준다. 
    • 더 이상 반복문을 돌 수 없을 때, 리턴을 하면서 만약 현재 노드가 얼리어 답터가 아니라면 나와 연결된 모든 노드가 얼리어답터야 하기 때문에 인접한 노드의 dp[인접한 노드][1]의 값을 현재 노드의 [0]에 해당하는 DP 값에 더한다.
    • 만약 현재 노드가 얼리어답터라면 2가지 경우가 존재한다.
      1. 인접한 노드가 얼리어답터 노드일 경우
      2. 인접한 노드가 얼리어답터가 아닌 노드일 경우
    • 이 둘 중 작은 DP 값을 현재 노드의 [1]에 해당하는 DP 값에 더한다.
  • DFS 함수를 마쳤다면 1번 노드에 dp[1][0] 값과 dp[1][1] 값 중 최솟 값이 최소한의 얼리어답터 수이므로 이를 결과로 출력한다.
    
    
    
    

3. 소스 코드

import java.io.*;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int N;
	static List<Integer>[] inList; // 인접리스트
	static int result = Integer.MAX_VALUE;
	static int[][] dp;  // dp[k][2] = r -> k노드가 얼리어답터이거나 얼리어답터가 아닐때 최소 얼리어답터 수 r
	static boolean[] visited;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		N = Integer.parseInt(br.readLine());
		
		// 인접리스트 초기화
		inList = new ArrayList[N + 1];
		for (int i = 1; i <= N; i++) {
			inList[i] = new ArrayList<>();
		}
		
		// 입력값으로 인접리스트 만들기
		for (int i = 0; i < N - 1; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			inList[from].add(to);
			inList[to].add(from);
		}
		
		// dp 초기화
		dp = new int[N + 1][2]; // 0 : 얼리X, 1: 얼리O
		
		// 방문배열 초기화
		visited = new boolean[N + 1];
		
		// 인접리스트의 DFS, 루트 노드부터 시작
		snsDFS(1);
		
		// 결과 출력
		bw.write(Integer.toString(Math.min(dp[1][0], dp[1][1])));
		bw.flush();
		bw.close();
		br.close();
	}
	
	// 인접리스트의 DFS
	private static void snsDFS(int idx) {
		
		// 방문 처리
		visited[idx] = true;
		
		// 얼리어답터가 아닌 경우는 0, 얼리어답터가 맞는 경우는 1
		dp[idx][0] = 0;
		dp[idx][1] = 1;
		
		for (int i = 0; i < inList[idx].size(); i++) {
			if (inList[idx].get(i) != null && !visited[inList[idx].get(i)]) {
				snsDFS(inList[idx].get(i));
				
				// 만약 현재 노드가 얼리어 답터가 아니라면 나와 연결된 모든 노드가 얼리어 답터여야 한다.
				dp[idx][0] += dp[inList[idx].get(i)][1];
						
				// 현재 노드가 얼리어답터라면 나랑 연결된 노드가 얼리어답터일 수도 있고 아닐 수도 있다.
				dp[idx][1] += Math.min(dp[inList[idx].get(i)][1], dp[inList[idx].get(i)][0]);
			}
		}
	}
}

4. 점수

70 / 100