문제링크

풀이1(직접 친구의 친구 탐색)

상근이의 동기들 친구관계를 인접리스트로 관리한다.
초대할 동기를 기록하기 위해 n+1 크기의 invited 배열을 선언한다.
1번(상근이)과 친구인 동기들을 true로 바꿔주고, 그 친구들의 친구까지 true로 바꿔준다.
이렇게 되면 1번(상근이)도 true인 상태가 되어버리니 마지막에 false로 바꿔주던가, 결과값에서 -1을 해주어야한다.

코드 1

package BOJ;

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

public class sol5567 {
    static int n, m;
    static boolean[] invited;
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        m = Integer.parseInt(br.readLine());

        invited = new boolean[n + 1];
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int i = 0; i < m; i++) {
            StringTokenizer 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);
        }

        for (int i = 0; i < graph.get(1).size(); i++) {	//	상근이와 친구인 동기들 체크
            int friend = graph.get(1).get(i);	
            invited[friend] = true;
            for (int j = 0; j < graph.get(friend).size(); j++) {	// 상근이의 친구의 친구인 동기들 체크
                int friend2 = graph.get(friend).get(j);
                invited[friend2] = true;
            }
        }

        invited[1] = false;	//	상근이를 제외시킴

        int count = 0;
        for (int i = 1; i <= n; i++) {
            if (invited[i]) {
                count++;
            }
        }
        System.out.println(count);
    }
}

풀이2(dfs)

위 방법은 직접적으로 친구와 친구의 친구를 확인하는 풀이라고 할 수 있다.
하지만 dfs를 사용하며 depth를 2까지만 계산하면 직접 확인하지 않아도 된다.

코드2(dfs)

package BOJ;

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

public class sol5567_2 {
    static int n, m;
    static boolean[] invited;
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        m = Integer.parseInt(br.readLine());

        invited = new boolean[n + 1];
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int i = 0; i < m; i++) {
            StringTokenizer 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(0, 1);

        int count = 0;

        for (int i = 2; i <= n; i++) {
            if (invited[i]) {
                count++;
            }
        }
        System.out.println(count);

    }

    public static void dfs(int depth, int friend) {
        if (depth == 2) {
            return;
        }
        for (int i : graph.get(friend)) {
            invited[i] = true;
            dfs(depth + 1, i);
        }
    }
}

큰 차이는 없는 것으로 확인된다..