[Java] 백준 DFS와 BFS

그래프

정점과 간선으로 이루어진 자료구조 G = ( V, E )

 

그래프 탐색

간선을 통해 모든 정점을 방문하는 것

 

그래프 탐색 방법

- 깊이 우선 탐색 DFS

- 너비 우선 탐색 BFS

 

DFS와 BFS

깊이 우선 탐색 DFS

• 깊이 우선 탐색은 그래프에서 노드의 자식들을 우선 탐색하는 방법이다.
• 위 그림을 보면 DFS는 1, 2, 4, 5, 3, 6, 7 순으로 탐색한다.
• DFS는 재귀함수나 스택 자료구조를 사용한다.
• 모든 노드를 방문하는 경우에 깊이 우선 탐색 방법을 선택한다.
• 검색 속도는 BFS보다 느리다.

 

너비 우선 탐색 BFS

• 너비 우선 탐색은 인접 노드를 먼저 탐색하는 방법이다.
• 위 그림에서 BFS는 1, 2, 3, 4, 5, 6, 7 순으로 탐색한다.
• BFS는 큐 자료구조를 사용한다.  
• 두 노드 사이 최단 경로나 임의의 경로를 찾고 싶을때 이 방법을 선택한다. 

※ BFS와 DFS 그래프 탐색의 특징은 노드의 방문 여부를 체크해줘야 한다는 점이다. 만약 검사하지 않는다면 무한루프에 빠질 위험이 있기 때문이다.

 

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

1260번: DFS와 BFS

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;

public class Main {
	static boolean[] check;
	static ArrayList<Integer> nodes[];
	static int N;
	public static void main(String[] args) {
		Scanner s= new Scanner(System.in);
	
		int N = s.nextInt(); //정점의 개수
		int M = s.nextInt(); //간선의 개수
		int V = s.nextInt(); //정점의 번호
		
		check =new boolean[N+1];
		nodes = new ArrayList[N+1];
		
		for(int i=1; i<=N; i++) {
			nodes[i] = new ArrayList();
			check[i]=false;
		}
		
		for (int i = 0; i < M; i++) {
			int n1 = s.nextInt();
			int n2 = s.nextInt();	
			nodes[n1].add(n2);  //노드 연결
			nodes[n2].add(n1);
			Collections.sort(nodes[n1]);
			Collections.sort(nodes[n2]);
			
	}
		

		dfs(V);
		System.out.println();
		
		//초기화
		for(int i=1; i<=N; i++) {
			check[i]=false;
		}
		
		bfs(V);

	}
	
	public static void dfs(int v) {
		Stack<Integer> stack=new Stack<Integer>();
		stack.push(v);
		
		while(!stack.isEmpty()) {
			int current = stack.pop();
			
			if(check[current]==false) {
				check[current]=true;
				System.out.print(current+" ");
				
				
				for(int i:nodes[current]) {
					if (check[i]==false)
						dfs(i);
				}
			}
			
		}
		
	}
	
	public static void bfs(int v) {
		Queue<Integer> que = new LinkedList();
		que.add(v); //시작점
		check[v] = true;
		
		while(!que.isEmpty()) {
			int current = que.poll();
			
			System.out.print(current+" ");
		
			  for(int i : nodes[current]){
	                if(check[i]==false){
	                    que.add(i);
	                    check[i] = true;
	                }
	                
	            }
			

		      
		}
		
	}
}