[백준]1260.DFS와 BFS/Java

📃DFS와 BFS 링크

👩🏻‍💻풀이

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class DFSBFS_1260 {
	static int[][] matrix;
	static boolean[] visited;

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
        
		int node = scan.nextInt();
		int edge = scan.nextInt();
		int start = scan.nextInt();
		
		matrix = new int[node+1][node+1];
		
		for(int i = 0; i < edge; i++) {
			int x = scan.nextInt();
			int y = scan.nextInt();
			matrix[x][y] = matrix[y][x] = 1;
		}
	
		visited = new boolean[node+1];
		dfs(start); 
		
		System.out.println();
        
		visited = new boolean[node+1];
		bfs(start);
	}
	
	public static void dfs(int start) {
		visited[start] = true;
		int count = 1;
		System.out.print(start+ " ");
		
		if(count == matrix.length - 1) 
			return;
		
		for(int i = 1; i < matrix.length; i++) {
			if(matrix[start][i] == 1 && visited[i] == false){
				count++;
				dfs(i);
			}
		}
	}
	
	public static void bfs(int start) {
		Queue<Integer> que = new LinkedList<Integer>(); 
		
		que.add(start);
		visited[start] = true;
 		System.out.print(start+ " ");
		
		while(!que.isEmpty()) {
			int check = que.peek();
			que.poll();
			for(int i = 1; i < matrix.length; i++) {
				if(matrix[check][i] == 1 && visited[i] == false) {
					que.add(i);
					visited[i] = true;
					System.out.print(i+ " ");
				}
			}
		}
	}
}

문제는 그래프를 DFS와 BFS를 이용하여 탐색하는 것 !

예제 입력 1
4 5 1
1 2
1 3
1 4
2 4
3 4

예제1번을 예시로 보면 DFS는 1-2-4-3, BFS는 1-2-3-4 순으로 탐색한다.

아래와 같은 순서로 코들르 작성했다
1. 인접행렬 만들기
2. DFS 메소드 - 재귀로 구현
3. BFS 메소드 - Queue(First In First Out)로 구현