백준 : 5567 (결혼식) (BFS)

이번문제 역시 각 노드별 BFS를 수행해나가면서 거리값을 갱신해 주는것이 핵심이다.

 

1번(나)로 부터 얼마만큼 떨어져있는지 알면, 친구인지 친구의 친구인지 알수 있기 때문이다.

 

if (visited[tmp] == false) { // 아직방문전
	dist[tmp] = dist[now] + 1; // 친구 관계 계산*****
	visited[tmp] = true; //방문표시
	q.offer(tmp);
}

import java.util.*;

class Main {

	static int n, m, start, end, resultCnt;
	static boolean[] visited;
	static int[] dist;
	static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();

	public static void bfs(int now) {
		Queue<Integer> q = new LinkedList<Integer>();
		q.offer(now);
		visited[now] = true; // 방문표시

		while (!q.isEmpty()) {
			now = q.poll();
			
			for (int i = 0; i < graph.get(now).size(); i++) {
				int tmp = graph.get(now).get(i);

				if (visited[tmp] == false) { // 아직방문전
					dist[tmp] = dist[now] + 1; // 친구 관계 계산*****
					visited[tmp] = true; //방문표시
					q.offer(tmp);
				}
			}
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		n = sc.nextInt();
		m = sc.nextInt();
		sc.nextLine();

		// 초기화
		visited = new boolean[n + 1];
		dist = new int[n + 1];
		for (int j = 0; j < n + 1; j++) { // 인덱스 0 사용안함 주의*****
			graph.add(new ArrayList<Integer>());
		}

		// 그래프 입력
		for (int j = 0; j < m; j++) {
			String st = sc.nextLine();
			String[] stArr = st.split(" ");

			int a = Integer.parseInt(stArr[0]);
			int b = Integer.parseInt(stArr[1]);

			graph.get(a).add(b);
			graph.get(b).add(a); // 양방향*****
		}

		bfs(1);

		for (int i = 0; i < dist.length; i++) {
			if (dist[i] > 0 && dist[i] <= 2) {
				resultCnt++;
			}
		}

		System.out.println(resultCnt);
	}
}