사회망 서비스(SNS)(BJ_G3_2533)

1. 문제 링크

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

 

 

---

 

2. 나의 코드

메모리: 426144kb
시간: 2288ms
코드 길이: 1741B
시간 복잡도 : O(N)
설명:
- 가장 중요한 것은 얼리어답터O, 얼리어탑더X 를 구분한다.
- 그 후 DFS를 사용하여 가장 하위 노드부터 값을 구하여 DP에 저장한다.

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

public class BJ_2533 {
    static int N;
    static int[][] dp;
    static boolean[] visited;
    static ArrayList<ArrayList<Integer>> graph;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        graph = new ArrayList<>();
        N = Integer.parseInt(br.readLine());
        dp = new int[N + 1][2]; // 0 : 얼리어탑터가 아닐 경우, 1 : 얼리어답터일 경우
        visited = new boolean[N + 1];
        // 그래프 생성
        for (int i = 0; i < N + 1; i++) {
            graph.add(new ArrayList<>());
        }
        // 트리 생성
        for (int i = 0; i < N - 1; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            graph.get(from).add(to);
            graph.get(to).add(from);
        }
        dfs(1, 1);
        System.out.println(Math.min(dp[1][1], dp[1][0]));
    }

    public static void dfs(int num, int depth) {
        dp[num][0] = 0; // 얼리어탑터가 아닐 경우는 0으로 초기화
        dp[num][1] = 1; // 얼리어탑터일 경우는 무조건 자신은 포함이므로 1로 초기화
        visited[num] = true;

        for (int next : graph.get(num)) {
            if (!visited[next]) {
                dfs(next, depth + 1);
                dp[num][0] += dp[next][1];
                dp[num][1] += Math.min(dp[next][0], dp[next][1]);
            }
        }
    }
}

 

---

 

3. 정답 코드

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

// 사회망 서비스(SNS)
// DP + 트리
public class p2533 {
	static int n;
	static boolean[] visited;
	static Node[] tree;
	// dp : 해당 지점까지의 얼리어답터 인원수(트리 구조이기 때문에 자식 노드들의 dp개수를 더해온다)
	static int[][] dp;	// [y][x]일 때, y : 노드 번호, x : 0 -> 해당 노드번호가 earlyAdaptor가 아닐때, 1 -> 해당 노드번호가 earlyAdaptor일 때
	
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.valueOf(br.readLine());
		dp = new int[n + 1][2];
		visited = new boolean[n + 1];
		tree = new Node[n + 1];
		StringTokenizer st;
		for(int i = 1; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			int start = Integer.valueOf(st.nextToken());
			int end = Integer.valueOf(st.nextToken());
			tree[start] = new Node(end, tree[start]);
			tree[end] = new Node(start, tree[end]);
		}
		
		// 트리 구조이기 때문에 1부터 시작
		dfs(1);
		System.out.println(Math.min(dp[1][0], dp[1][1]));
	}
	
	static void dfs(int number) {
		visited[number] = true;
		dp[number][0] = 0;
		dp[number][1] = 1;
		
		for(Node next = tree[number]; next != null; next = next.next) {
			if(!visited[next.n]) {	// dfs 중복 방문 방지(안해도되는데 확인해보기)
				dfs(next.n);	// dfs 재귀호출을 통해 자식 노드의 dp값을 미리 구한다.
				dp[number][0] += dp[next.n][1];	// 자식 노드가 무조건 얼리어답터여야한다.
				dp[number][1] += Math.min(dp[next.n][0], dp[next.n][1]);	// 왜냐하면 최소의 얼리어답터 인원을 뽑기 때문에 자식 노드가 얼리어답터 일수도, 아닐수도 있다.
			}
		}
	}
}

class Node {
	int n;
	Node next;
	
	public Node(int n, Node next) {
		this.n = n;
		this.next = next;
	}
}

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

public class Main_2533 {

	// 현재 노드를 루트로 하는 트리의 얼리 어답터 최소 수
	public static void go(int node) {
		visited[node] = true;
		dp[node][0] = 1;
		
		for(int nextNode : edgeList.get(node)) {
			if(visited[nextNode]) continue;
			go(nextNode);
			dp[node][1] += dp[nextNode][0];
			dp[node][0] += Math.min(dp[nextNode][0], dp[nextNode][1]);
		}
	}
	
	static int dp[][];
	static List<List<Integer>> edgeList;
	static boolean visited[];
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		edgeList = new ArrayList<>();
		for(int i=0;i<=N;i++) {
			edgeList.add(new ArrayList<>());
		}
		
		for(int i=0;i<N-1;i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			edgeList.get(u).add(v);
			edgeList.get(v).add(u);
		}
		
		// 현재 노드를 루트로 하는 트리에서 현재 노드가 얼리어답터일 때와 아닐 때 필요한 얼리어답터 수
		dp = new int[N+1][2];
		
		// 방문한 노드 
		visited = new boolean[N+1];
		
		go(1);
		
		System.out.println(Math.min(dp[1][0], dp[1][1]));
		
	}

}

 

---

 

4. 배운 점

- 오랜만에 알고리즘을 풀었다. 그래서 너무 어렵긴 했다.

- 처음으로 이 문제를 접근한 방법은 서로소 집합으로 접근 했는데 실패 했다.

- 그리고 나서 위상정렬을 사용해보려고 했으나 실패 했다.

- 이렇게 범위가 매우 크고 XX인지 YY인지 같은 문제는 DP를 사용해보려고 노력해야 겠다.