그래프 알고리즘 예제(6). 백준 [1260] DFS와 BFS

백준[1260] - DFS와 BFS

그래프 탐색의 기본인 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)을 구현하는 문제를 풀어보았다.

예전에 공부해서 잘 할 수 있으려나 하고 생각했는데 생각보다 잘 풀렸다. 
역시 기본 개념을 이해하고 있다면 구현하기 쉬운 거 같다.

DFS에서는 재귀를 이용한다는 점을 알고 구현하니 훨씬 순조로웠다. 
또한 BFS에서 Queue를 사용한다는 키포인트를 알고있었기 때문에 쉽게 문제를 풀 수 있었다.

 

DFS에서는 방문하지 않은 노드일 경우 출력을 하고, 해당 노드에서 갈 수 있는 노드를 하나씩 dfs()를 이용하여 재귀시키면 간단하게 풀린다. 그렇게 재귀 호출되어 탐색을 시작한 노드에서도 똑같은 작업을 수행하기 때문에 최대한 탐색할 수 있는 노드까지 최대한 순회한 뒤 반환되어 나머지 노드를 순회한다.

 

BFS에서는 시작 노드를 Queue에 넣어 시작한다. 만약 이 Queue가 비어있지 않다면 노드를 하나씩 꺼내어 방문했는지 여부를 확인한 뒤, 방문하지 않은 노드라면 출력을 하고 그 노드에서 탐색 가능한 모든 노드를 Queue에 넣는다.
그 뒤에 다시 Queue가 비어있는지 확인하는 과정을 반복하게 된다. Queue는 FIFO방식의 자료구조이기 때문에 먼저 넣은 노드가 먼저 처리하게 되며 이는 너비를 우선적으로 순회하는 BFS가 된다.

 

 

다음은 Java로 작성한 코드이다. 

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

public class DFSandBFS {
	//그래프
	static ArrayList<ArrayList<Integer>> graph;
	//방문 여부 저장 배열
	static boolean visited[];
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int nodeNum = scan.nextInt();
		int edgeNum = scan.nextInt();
		int startNode = scan.nextInt();
		visited = new boolean[nodeNum+1];
		
		//그래프가 양방향이고 정렬을 해야 하기 때문에 Comparator 생성
		Comparator<Integer> c = new Comparator<Integer>() {

			@Override
			public int compare(Integer o1, Integer o2) {
				return o1 - o2;
			}
		};

		graph = new ArrayList<ArrayList<Integer>>();


		//입력 및 초기화
		for (int i = 0; i <= nodeNum; i++) {
			graph.add(new ArrayList<Integer>());
		}

		for (int i = 0; i < edgeNum; i++) {
			int start = scan.nextInt();
			int end = scan.nextInt();

			graph.get(start).add(end);
			graph.get(end).add(start);
		}

		//정렬
		for (int i = 0; i <= nodeNum; i++) {
			graph.get(i).sort(c);
		}

		//깊이 우선 탐색
		dfs(startNode);
		
		//방문여부 초기화
		for (int i = 0; i <= nodeNum; i++) {
			visited[i] = false;
		}
		System.out.println();
		
		//너비 우선 탐색
		bfs(startNode);
	}

	static void dfs(int start) {
		if(visited[start]) {
			return;
		}
		visited[start] = true;
		System.out.print(start+" ");
		for(int n : graph.get(start)) {
			dfs(n);
		}
	}

	static void bfs(int start) {
		Queue<Integer> q = new LinkedList<Integer>();

		q.add(start);
		while(!q.isEmpty()) {
			int temp = q.poll();
			if(visited[temp]) {
				continue;
			}
			System.out.print(temp+" ");
			visited[temp] = true;
			for(int n : graph.get(temp)) {
				q.add(n);
			}
		}

	}
}