[백준 1260] DFS와 BFS

문제

풀이

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

class Main {
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
        
		int point = scan.nextInt();
		int line = scan.nextInt();
		int start = scan.nextInt();
		
		int[][] arr = new int[point+1][point+1]; // 그래프 생성
		
		for(int i=1;i<=line;i++) {
			int a = scan.nextInt();
			int b = scan.nextInt();
			arr[a][b] = 1;
			arr[b][a] = 1;
		}
		
        // 깊이우선탐색
		boolean[] visited = new boolean[point+1];
		dfs(arr, visited, start); 
		
		System.out.println();
        
        // 너비우선탐색
		boolean[] visited2 = new boolean[point+1];
		bfs(arr, visited2, start); 

		
	}
	public static void dfs(int[][] arr, boolean[] visited, int start) {
		visited[start] = true;
		System.out.print(start + " ");

		
		for (int i = 1; i < arr.length; i++) {
			int next = arr[start][i];
			if (next == 1 && !visited[i]) {
				dfs(arr, visited, i);
			}
		}
			
	}
	public static void bfs(int[][] arr, boolean[] visited, int start) {
		visited[start] = true;
		System.out.print(start + " ");
		
		Queue<Integer> queue = new LinkedList<Integer>();
		queue.add(start);
		
		while(!queue.isEmpty()) {
			int visit = queue.poll();
			for (int i = 1; i < arr.length; i++) {
				if (arr[visit][i] == 1 && !visited[i]) {
					queue.add(i);
					visited[i] = true;
					System.out.print(i+ " ");
				}
			}
		}
	}

}

• DFS는 깊이우선탐색으로, 한 노드에 연결되어있는 childNode를 끝까지 탐색한다.
• BFS는 너비우선탐색으로, 한 노드의 childNode를 모두 탐색한 후, childNode의 childNode 순으로 들어가 탐색한다.
• BFS는 큐에 한 노드에 연결되어있는 1차 자식노드를 모두 넣는다. 1차 자식노드를 넣은 후 해당 자식노드의 자식노드를 다시 큐에넣고 탐색한다.

출처: https://www.acmicpc.net/problem/1260