[백준_1260번] DFS와 BFS

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

1260번: DFS와 BFS

[문제]

 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

 

[입력 조건]

 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

 

[코드]

import java.util.*;

public class BaekJoon_1260 {
	public static boolean[] dfsvisited=new boolean[1001];
	public static boolean[] bfsvisited=new boolean[1001];
	public static int[][] graph=new int[1001][1001];
	public static int n,m,v;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt(); // 노드 개수
		m=sc.nextInt(); // 간선 개수
		v=sc.nextInt(); // 시작점 
		
		// 간선 연결상태 저장
		for(int i=1;i<=m;i++) {
			int a=sc.nextInt();
			int b=sc.nextInt();
			
			// 노드 a와 b는 연결되어 있다는 표시
			graph[a][b]=graph[b][a]=1;
		}
		
		DFS(v);
		System.out.println();
		BFS(v);
	}
	
	// 깊이 우선 탐색
	public static void DFS(int x) {
		dfsvisited[x]=true; // 방문처리
		System.out.print(x+" "); // 경로 출력
		
		// 현재 노드와 연결되어 있고, 방문하지 않은 노드가 있다면 재귀호출
		for(int i=1;i<=n;i++) {
			if(graph[x][i]==1&&dfsvisited[i]==false)
				DFS(i);
		}
	}
	
	// 너비 우선 탐색
	public static void BFS(int start) {
		Queue<Integer> queue=new LinkedList<Integer>(); // 큐 선언
		queue.offer(start); // 시작 노드 삽입
		bfsvisited[start]=true; //  방문처리
		
		while(!queue.isEmpty()) {
			int x=queue.poll(); 
			System.out.print(x+" "); // 경로 출력
			
			// 현재 노드와 연결되어 있고, 방문하지 않은 노드가 있다면 재귀호출
			for(int i=1;i<=n;i++) {
				if(graph[x][i]==1&&bfsvisited[i]==false) {
					queue.offer(i); // 큐에 노드 삽입
					bfsvisited[i]=true; // 방문처리
				}
			}
		}
	}
}

 

[고찰]

 DFS(깊이 우선 탐색)은 최대한 멀리있는 노드부터 우선탐색 하는 방법으로 스택과 재귀함수를 이용하여 구현한다. 반면에 BFS(너비 우선 탐색)은 최대한 가까이있는 노드부터 우선탐색 하는 방법으로 큐와 큐 자료구조를 이용하여 구현한다.