5567_결혼식

사용 알고리즘: bfs

사용 언어: java

 

package week34;

import java.util.*;
public class Main_bj_5567_결혼식 {
	static int n,m, answer;
	static List<Integer>[] list;

	public static void main(String[] args) {
		init_5567();

		bfs_5567();
		
		System.out.println(answer);
	}

	private static void bfs_5567() {
		boolean[] visit = new boolean[n+1];
		visit[1] = true;
		Queue<int[]> q = new ArrayDeque<>();
		q.add(new int[] {1, 0});
		while(!q.isEmpty()) {
			int[] p = q.poll();
			
			if(p[1]+1 >= 3) continue;
			
			for (int nxt : list[p[0]]) {
				if(!visit[nxt] && p[1]+1 < 3) {
					visit[nxt] = true;
					q.add(new int[] {nxt, p[1]+1});
					answer ++;
				}
			}
		}
	}

	private static void init_5567() {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		m = sc.nextInt();
		list = new ArrayList[n+1];
		for (int i = 0; i < list.length; i++) {
			list[i] = new ArrayList<>();
		}
		
		for (int i = 0; i < m; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			list[a].add(b);
			list[b].add(a);
		}
	}

}

 

 

예전에는 dfs로 풀어서 뭔가 틀렸었다.

1의 친구이면서 + 1의 친구의 친구인 경우 (1,2,3이 다 친구인 경우) cnt처리를 안 해주어서 틀렸던 거 같다.

(2와 3이 1의 친구로도, 서로의 친구(친구의 친구)로도 cnt되어서 그랬던 듯)