[BOJ] 백준 5567번 결혼식 (Java)

#5567 결혼식

난이도 : 실버 1

유형 : 그래프 / DFS

5567번: 결혼식

▸ 문제

상근이는 자신의 결혼식에 학교 동기 중 자신의 친구와 친구의 친구를 초대하기로 했다. 상근이의 동기는 모두 N명이고, 이 학생들의 학번은 모두 1부터 N까지이다. 상근이의 학번은 1이다.

상근이는 동기들의 친구 관계를 모두 조사한 리스트를 가지고 있다. 이 리스트를 바탕으로 결혼식에 초대할 사람의 수를 구하는 프로그램을 작성하시오.

▸ 입력

첫째 줄에 상근이의 동기의 수 n (2 ≤ n ≤ 500)이 주어진다. 둘째 줄에는 리스트의 길이 m (1 ≤ m ≤ 10000)이 주어진다. 다음 줄부터 m개 줄에는 친구 관계 ai bi가 주어진다. (1 ≤ ai < bi ≤ n) ai와 bi가 친구라는 뜻이며, bi와 ai도 친구관계이다.

▸ 출력

첫째 줄에 상근이의 결혼식에 초대하는 동기의 수를 출력한다.

 

문제 풀이  

그래프 탐색 문제로 BFS, DFS 편한 방법을 사용하면 된다. 나는 친구의 친구 즉, 1번 노드로부터 거리가 2인 정점까지만 구하는 탐색이므로 깊이 탐색인 DFS를 사용했다. 거리가 2인 정점까지 모든 리스트를 탐색하게 되면 대략 잡아도 1억정도이므로 사용할만 하다.

 

설계

1. 1번 노드를 기준으로 DFS 탐색을 한다. dfs(1,0);
2. 거리가 2 초과인 친구는 더이상 탐색하지 않는다. if(depth>2) return;
3. 거리가 2 이하인 친구는 초대할 리스트에 추가한다. if(pos!=1 && !ans.contains(pos)) ans.add(pos);
4. 거리는 다음과 같이 세준다.
   1. if(pos==1) 1번 노드와 직접적으로 연결되어있는 경우 dfs(nxt, depth+1);
   2. if(depth!=0) 1번 노드와 연결되어 있지 않은 경우 1번 노드와 이어진 노드 즉, depth가 1인 이상인 노드만 계속해서 탐색한다. dfs(nxt, depth+1);

 

풀이 코드 

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

public class Main {
	static List<Integer>[] list;
	static List<Integer> ans;
	static boolean[] check;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		int m = Integer.parseInt(br.readLine());
		
		check = new boolean[n+1];
		ans = new ArrayList<>();
		list = new ArrayList[n+1];
		for(int i=0; i<n+1; i++) {
			list[i] = new ArrayList<>();
		}
		
		StringTokenizer st = null;
		for(int i=0; i<m; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			list[a].add(b);
			list[b].add(a);
		}
		check[1] = true;
		dfs(1,0);
		
		System.out.println(ans.size());
	}
    
	static void dfs(int pos, int depth) {
		if(depth>2) return;
			
		if(pos!=1 && !ans.contains(pos)) {
			ans.add(pos);
		}
		
		check[pos] = true;
		for(int nxt : list[pos]) {
			if(check[nxt]) continue;
			
			if(pos==1) {
				dfs(nxt, depth+1);
			}else {
				if(depth!=0) {
					dfs(nxt, depth+1);
				}
			}
		}
		check[pos] = false;
	}
}