[백준 Gold 3] 2553 사회망 서비스(SNS) - Java

문제링크 : https://www.acmicpc.net/problem/2533

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

 

접근 과정 : 

• 각 친구는 얼리어답터이거나 일반인이다.
• 즉 노드의 상태가 0,1인 경우에 따라서, 최소 얼리어답터의 수를 저장하는 DP를 사용했다.
• DP[][] : i가 얼리어답터(1) 이거나 일반일(0)일 때, 최소 얼리어답터의 수를 의미한다. 
• 그리고 친구 관계를 저장하는 데 있어서, List를 활용 /  node 클래스 작성 두가지 방법으로 시도해보았다. 

 

소스 코드 및 결과 :

package BOJ;

/**
 
    사회망 서비스(SNS)
    
    List<List<Integer>> 에 친구관계 저장.

 */

import java.io.*;
import java.util.*;

public class BOJ2533_copy {

    public static void main(String[] args) throws NumberFormatException, IOException {

        init();

        findDP(1);

        System.out.println(Math.min(dp[1][0], dp[1][1]));

    }

    static int N;
    static List<List<Integer>> friends;
    static int[][] dp; // i번 친구가 얼리어답터인 경우 = 1 / 아닌 경우 = 0
    static boolean[] visit;

    static void init() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        friends = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            friends.add(new LinkedList<>());
        }

        for (int i = 1; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            friends.get(a).add(b);
            friends.get(b).add(a);
        }

        dp = new int[N + 1][2];
        visit = new boolean[N + 1];
    }

    static void findDP(int x) {

        visit[x] = true;
        dp[x][1] = 1;

        for (int friend : friends.get(x)) {
            if (visit[friend]) {
                continue;
            }

            findDP(friend);

            dp[x][0] += dp[friend][1];
            dp[x][1] += Math.min(dp[friend][0], dp[friend][1]);
        }

    }
    

}

 

package BOJ;

/**
 
    사회망 서비스(SNS)
    
    Node 클래스 생성해서 사용

 */

import java.io.*;
import java.util.*;

public class BOJ2533 {

    public static void main(String[] args) throws NumberFormatException, IOException {

        init();

        findDP(1);

        System.out.println(Math.min(dp[1][0], dp[1][1]));

    }

    static int N;
    static Node[] sns;
    static int[][] dp; // i번 친구가 얼리어답터인 경우 = 1 / 아닌 경우 = 0
    static boolean[] visit;

    private static class Node {
        int num;
        Node friend;

        Node(int num, Node friend) {
            this.num = num;
            this.friend = friend;
        }

    }

    static void init() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        sns = new Node[N + 1];

        for (int i = 1; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            add(a, b);
            add(b, a);

        }

        dp = new int[N + 1][2];
        visit = new boolean[N + 1];
    }

    static void add(int root, int f) {

        if (sns[root] == null) {
            sns[root] = new Node(f, null);
        } else {
            sns[root] = new Node(f, sns[root]);
        }
    }

    static void findDP(int x) {

        visit[x] = true;
        dp[x][1] = 1;
        
        for (Node f = sns[x]; f != null; f = f.friend) {

            if (visit[f.num]) {
                continue;
            }


            findDP(f.num);

            dp[x][0] += dp[f.num][1];
            dp[x][1] += Math.min(dp[f.num][0], dp[f.num][1]);

        }

    }


}

 

P.S 

사실 의문점이 생긴 문제였다.

List를 활용해서 푸는 방식과 Node Class를 생성하는 방식의 시간차이가 매우 크더라.. 이유를 알고싶다..

 

누가 좀 알려주세요!!