문제 : 결혼식

문제링크
실버 2
그래프 탐색

결혼식에 초대할 사람 수 구하기
초대할 사람은 친구와 친구의 친구이다.
사람은 학번(1~n)으로 구분되며 상근이는 1이다.

입력

상근이 동기 수 n (2<=n&&500>=n)
리스트의 길이 m
친구관계 a,b m줄

출력

최소 이동 수 입력 순으로 출력

풀이

1. 그래프 1의 자식 노드들을 시작점으로 dfs한다. (예시1 같은 경우가 있으므로 방문여부와 상관없이 모두 시작점으로해서 탐색한다)
2. 이전에 방문하지 않은 노드라면 cnt++해준다.
3. 방문한 노드라면 카운트 하지않고 자식 노드 탐색만 해준다.
4. dfs 함수는 visited 체크해서 자식노드가 있을 때 cnt 해준다.

코드

import java.util.ArrayList;
import java.util.Scanner;


public class 백준5567 {
	static int n,m,cnt=0;
	static ArrayList<ArrayList<Integer>> list=new ArrayList<>();
	static boolean[] visited;
	static Scanner scan =new Scanner(System.in);
	static StringBuilder sb=new StringBuilder();
	public static void main(String[] args) {
		// 입력
		n=scan.nextInt();
		m=scan.nextInt();
		for(int i=1;i<=n+1;i++) {
			list.add(new ArrayList<Integer>());
		}
		visited=new boolean[n+1];
		for(int i=0;i<m;i++) {
			int a=scan.nextInt();
			int b=scan.nextInt();
			list.get(a).add(b);
			list.get(b).add(a);
			}
		visited[1]=true;
		for(int i=0;i<list.get(1).size();i++) {
			if(!visited[list.get(1).get(i)]) {
				visited[list.get(1).get(i)]=true;
				dfs(list.get(1).get(i),1);	
				cnt++;
			}
			else {
				dfs(list.get(1).get(i),1);	
			}
		}
	
		System.out.print(cnt);

	}
	static void dfs(int i, int depth) {
		if(depth==2) {
			cnt++;
			return ;
		}
		for(int k=0;k<list.get(i).size();k++) {
			if(list.get(i).get(k)!=null&&!visited[list.get(i).get(k)]) {
				visited[list.get(i).get(k)]=true;
				dfs(k,depth+1);
			}
		}
	}

}