[BFS/DFS] 너비우선탐색/깊이우선탐색

맹목적 탐색

이미 정해진 순서에 따라 상태 공간 그래프를 점차 형성해 가면서 해를 탐색하는 방법

대표적인 맹목적 탐색 : 너비우선탐색(BFS), 깊이우선탐색(DFS)

 

너비우선탐색 (BFS;Breadth First Search)

하나로 시작 정점을 방문한 후 시작 정점에 인접함 모든 정점들을 우선 방문하는 방법

갈림길에 연결되어 있는 모든 길을 한번씩 탐색한 뒤 다시 연결되어있는 모든 길을 탐색하는 방법

너비우선탐색은 트리나 그래프를 방문 또는 탐색하는 방법으로 순서는 다음과 같다

1. 루트에서 시작

2. 루트의 자식 노드들을 [1]에 저장

3. [1]에 저장된 노드들을 차례로 방문 후 각각 자식들을 [2]에 저장

4. [2]에 저장된 노드들을 차례로 방문 후 각각 자식들을 [3]에 저장

5. 위의 과정을 반복한 후 모든 노드 방문 후 탐색을 종료

[구현소스코드]

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

public class Main {
	static int V;	// 정점의 개수
	static int E;	// 간선의 개수
	static int[][] arr;	// 정점 간 연결관계 저장 배열
	static boolean[] check;	// 방문한 정점 체크 배열
	
	static void bfs(int n) {
		Queue<Integer> queue = new LinkedList<>();	//Queue는 FIFO임
		
		queue.offer(n);	// Root node를 Queue에 넣음
		
		while(!queue.isEmpty()) {
			int temp = queue.poll();	//방문한 정점 뺌
			
			for(int i = 1; i < V+1; i++) {
				if(arr[temp][i]==1 && check[i]== false) {
					queue.offer(i);		//방문한 정점 추가
					check[i] = true;	//방문했으므로 true로 바꿈
				}
			}
		}
	}
	public static void main(String[] args) {
	       Scanner sc = new Scanner(System.in);
	       
	       V = sc.nextInt();
	       E = sc.nextInt();
	       
	       arr = new int[V+1][V+1];		//0으로 초기화
	       check = new boolean[V+1];	//false으로 초기화
	       
	       for(int i=0; i < E; i++) {
	    	   int tmp1 = sc.nextInt();
	    	   int tmp2 = sc.nextInt();
	    	   arr[tmp1][tmp2] = 1;
	       }
	       
	       int n = sc.nextInt();	//탐색시작 위치
	       bfs(n);
	}
}

참조 : https://seeminglyjs.tistory.com/255

 

깊이우선탐색 (DFS;Depth First Search)

탐색트리에서 한 루트로 탐색하다가 특정 상황에서 최대한 깊숙히 들어가면서 탐색한 후

다시 한 레벨씩 올라가(BackTracking : 백트래킹) 다른 루트로 탐색하는 방식

갈림길이 나타날 때마다 '다른 길이 있음' 정보 기록한 후 자신이 지나간 길을 지워나감

막다른 곳에 도달하면 직전 갈림길로 돌아가면서 '이 길은 아님' 표식을 남김

[구현소스코드]

import java.util.Scanner;

public class Main {
	static int V;	// 정점의 개수
	static int E;	// 간선의 개수
	static int[][] arr;	// 정점 간 연결관계 저장 배열
	static boolean[] check;	// 방문한 정점 체크 배열
	
	static void dfs(int n) {
		for(int i = 1; i < arr[n].length+1; i++) {
			if(arr[n][i]==1 && check[i]==false) {
				dfs(i);
			}
		}
		check[n] = true;	//해당 정점을 모두 방문한 후 true 바꿈
	}
	public static void main(String[] args) {
	       Scanner sc = new Scanner(System.in);
	       
	       V = sc.nextInt();
	       E = sc.nextInt();
	       
	       arr = new int[V+1][V+1];		//0으로 초기화
	       check = new boolean[V+1];	//false으로 초기화
	       
	       for(int i=0; i < E; i++) {
	    	   int tmp1 = sc.nextInt();
	    	   int tmp2 = sc.nextInt();
	    	   arr[tmp1][tmp2] = 1;
	       }
	       
	       int n = sc.nextInt();	//탐색시작위치
	       dfs(n);
	}
}

위의 너비우선탐색을 토대로 깊이우선탐색 코드를 작성해 보았다

개념을 토대로 DFS/BFS 관련 문제들을 풀어봐야겠다!

 

[참조]

나무위키 : https://namu.wiki/w/깊이%20우선%20탐색