[BOJ/Java] 백준 5567번 - 결혼식

백준 #5567 결혼식

5567번: 결혼식

 

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

public class Main {
	
	static int n, m, cnt;
	static List<ArrayList<Integer>> friends;
	static int[] visited;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());  // 상근이 동기 수
		m = Integer.parseInt(br.readLine());  // 리스트 길이
		
		// 친구 관계 저장
		friends = new ArrayList<>();
		for (int i = 0; i <= n; i++) {
			friends.add(new ArrayList<Integer>());
		}
		
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int v1 = Integer.parseInt(st.nextToken());
			int v2 = Integer.parseInt(st.nextToken());
			friends.get(v1).add(v2);
			friends.get(v2).add(v1);
		}
		
		visited = new int[n+1];  // 방문 및 이동 깊이 저장
		bfs();
		System.out.println(cnt);
		
	}
	
	public static void bfs() {
		Queue<Integer> q = new LinkedList<Integer>();
		q.offer(1);
		visited[1] = 1;
		while (!q.isEmpty()) {
			int w = q.poll();
			if (visited[w] == 3) return;
			for (int v : friends.get(w)) {
				if (visited[v] == 0) {
					visited[v] = visited[w] + 1;
					q.offer(v);
					cnt++;
				}
			}
		}
	}
}

BFS 탐색을 이용했다. 이때 방문 표시를 boolean으로 하지 않고, 시작 노드에서 총 몇 번 이동했는지 횟수를 저장했다. 횟수를 저장할 때 방문한 노드 개수도 +1 해주어 초대하는 동기 수도 세준다. 이동 횟수가 3이 되면 친구의 친구를 넘어간 것으로 탐색을 종료한다.