[백준] 5567 결혼식 - BFS(너비우선탐색) + DFS(깊이우선탐색) JAVA

https://www.acmicpc.net/problem/5567

코드설명

BFS(너비우선탐색) + DFS(깊이우선탐색) 를 활용합니다.

 

BFS의 QSize만큼을 미리 연산해와서 각 턴마다 친구를 세도록 합니다.

코드

BFS를 활용한 코드입니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
	static int N, C, H, W, K, M, T;
	static int answer = 0;
	static int[][] matrix;
	
	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()); // 동기의 수
		st = new StringTokenizer(br.readLine());
		M = Integer.parseInt(st.nextToken());
		
		matrix = new int[N][N];
		for(int i=0;i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken()) - 1;
			int b = Integer.parseInt(st.nextToken()) - 1;
			
			matrix[a][b] = 1;
			matrix[b][a] = 1;
		}
		System.out.println(BFS());
	}
	
	public static int BFS() {
		Queue<Integer> q = new LinkedList<>();
		q.offer(0);
		boolean[] visited = new boolean[N];
		visited[0] = true;
		
		int qSize = q.size();
		int depth = 0;
		int ret = 0;
		while(qSize-- > 0 && depth < 2) {
			int now = q.poll();
			for(int next = 0; next < N; next++) {
				if(matrix[now][next] == 1 && visited[next] == false) {
					visited[next] = true;
					q.offer(next);
				}
			}
			
			if(qSize == 0) {
				depth += 1;
				qSize = q.size();
				ret += qSize;
			}
			
		}
		return ret;
	}
	
}

 

처음에 잘못 푼 코드입니다. DFS로 할경우 모든 친구들에서 가능한 경우를 생각해내지 못합니다.

아래의 코드에서 HashSet을 활용할경우 해결은 되겠지만, BFS로 처리하면 더 간단해집니다.

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
	static int N, C, H, W, K, M, T;
	static int answer = 0;
	static int[][] matrix;
	
	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()); // 동기의 수
		st = new StringTokenizer(br.readLine());
		M = Integer.parseInt(st.nextToken());
		
		matrix = new int[N][N];
		for(int i=0;i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken()) - 1;
			int b = Integer.parseInt(st.nextToken()) - 1;
			
			matrix[a][b] = 1;
			matrix[b][a] = 1;
		}
		
		boolean[] visited = new boolean[N];
		visited[0] = true;
		System.out.println( DFS(0, 0, visited) );
		
	}
	
	static int DFS(int depth, int now, boolean[] visited) {
		if(depth == 2) {
			return 0;
		}
		
		int ret = 0;
		for(int next = 0; next < N; next++) {
			System.out.println("now:"+now+"next:"+next);
			if((matrix[now][next] == 1 && visited[next] == false )) {
				System.out.println("next:"+next);
				visited[next] = true;
				ret += DFS(depth + 1, next, visited) + 1;
			}
		}
		return ret;
	}
	
}