문제 이해

친구 관계가 주어질 것이다.
그리고 '나'는 1이다.
1의 친구, 1의 친구의 친구까지만 결혼식에 초대하려한다.

이 때 총 몇 명의 사람을 초대할 것인지 구하라.

---

문제 풀이

그래프에서 1개, 혹은 2개의 간선을 거쳐 갈 수 있는 모든 점들을 출력하는 문제이다.

가중치는 없고, 중간에 거친 Edge수를 셀 필요가 있다.

따라서, BFS를 통해 문제를 해결하였다.

---

코드

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

class Count{
	int x;
	int length;
	
	public Count(int x,int length) {
		this.x = x;
		this.length = length;
	}
}

public class Main {
	static StringBuilder sb = new StringBuilder();
	static int N,M;
	static ArrayList<Integer>[] lists;
	
	static void bfs() {
		int start = 1; // 시작점은 1
		
		Queue<Count> counts = new LinkedList<>();
		counts.add(new Count(start,0));
		int sum = 0;
		boolean[] visit = new boolean[N+1];
		
		while(!counts.isEmpty()) {
			Count tmp = counts.poll();
			
			if(visit[tmp.x]) continue; 
            // 방문했던 점에 대한 중복 처리는 필요 없음
            
			if(tmp.length>2) break; 
            // 길이가 2 초과로 변했다는 것은 BFS 특징 상 다음 조사할 Node들도 
            // 모두 길이가 2 초과일 것이다.
            // 우리는 길이가 1, 2인 점들만 찾고 싶기 때문에
            // 바로 반복문을 종료시키면 된다.
			
			visit[tmp.x] = true;
			sum++;
			
			for(int s:lists[tmp.x]) {
				counts.add(new Count(s,tmp.length+1));
			}
		}
		System.out.println(sum - 1); 
        // 1은 나 자신이므로, 결과값에서 빼줘야 한다.
	}
	
	public static void main(String[] args) {

		FastReader sc = new FastReader();
		
		N = sc.nextInt();
		M = sc.nextInt();
		lists = new ArrayList[N+1];
		
		for(int i =0;i<N+1;i++) {
			lists[i] = new ArrayList<>();
		}
		
		for(int i =0;i<M;i++) {
			int tmp1 = sc.nextInt();
			int tmp2 = sc.nextInt();
			
			lists[tmp1].add(tmp2);
			lists[tmp2].add(tmp1);
		}
		
		bfs();
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

---

결과