[Data Structure][JAVA]DFS, BFS 구현

DFS(Deepth - Frist - Search): 깊이 우선 탐색

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

public class Main {
	
	public static boolean[] visited = new boolean[9];
	public static int[][] graph = {{}, {2,3,8},{1,7},{1,4,5},{3,5},{3,4},{7},{2,6,8},{1,7}};
	
	public static void dfs(int x) {
		visited[x] = true;
		System.out.print(x + " ");
		
		for(int i = 0; i < graph[x].length; i++) {
			int y = graph[x][i];
			if(!visited[y]) dfs(y);
		}
	}
	
	public static void main(String[] args) {	
		dfs(1);
	}			
}

• 스택을 이용해 인접한 노드로 이동하며 탐색하는 과정이다.
• 정보처리기사에서 공부한 그대로이다.
• 다만 손으로 적어가면서 문제 푸는거랑 다른 점은
• 방문한 노드의 값을 저장해 둔 다음 해당 내용을 사용한다는 점이다.

 

BFS(Breadth - Frist - Search): 너비 우선 탐색

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

public class Main {
	
	public static boolean[] visited = new boolean[9];
	public static int[][] graph = {{}, {2,3,8},{1,7},{1,4,5},{3,5},{3,4},{7},{2,6,8},{1,7}};

	public static void bfs(int start) {
		Queue<Integer> q = new LinkedList<>();
		
		q.offer(start);
		visited[start] = true;
		
		while(!q.isEmpty()) {
			int x = q.poll();
			System.out.print(x + " ");
			
			for(int i = 0; i < graph[x].length; i++) {
				int y = graph[x][i];
				if(!visited[y]) {
					q.offer(y);
					visited[y] = true;	
					// 삽입 후 바로 방문처리 해줘야 다른 노드에서 중복 접근 안함
				}
			}
		}
	}
	
	public static void main(String[] args) {	
		bfs(1);
	}			
}

• 큐를 이용해서 인접한 노드를 이동하며 탐색하는 과정이다.
• 접근한 노드를 체크하는 점을 주목해야한다.
• 큐에 해당 노드를 넣은 후 바로 방문 처리를 해줘야 한다.
• 아니면 노드 순회 시 왔던길을 다시 갈 수 있기 때문이다.