[백준 1260] DFS와 BFS 프로그램

문제 : 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오.

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

 

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

 

출력 : 

1번째 줄에 DFS를 수행한 결과, 그다음 줄에 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

 

 

문제접근 방법 : 

 

위 문제는 방향성을 갖지 않는 그래프를 나타낸다. 또한, 방문할 수 있는 정점이 여러 개일경우, 정점 번호가 작은 것부터 방문한다 했으므로, 각 요소들의 인접 노드를 오름 차순으로 정렬해야한다.

 

1. 각 연결된 요소들은 그래프 형태를 띄고있다. 따라서, 이러한 데이터들을 저장하기 위해 인접리스트에 데이터들을 저장해야한다.

인접리스트

 

 

 

2.  DFS의 경우, 재귀함수 형태로 구현한다. 

3.  BFS의 경우, Queue로 구현한다.

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


public class Main {

	static boolean[] visited;
	static ArrayList<Integer>[] A;	
    
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt(); // 노드 개수
		int M = sc.nextInt(); // 에지 개수
		int Start = sc.nextInt(); // 시작점
		
		A = new ArrayList[N+1]; // 인접노드를 저장할 배열리스트
		
		for(int i=1; i<=N; i++) {
			A[i] = new ArrayList<Integer>();
		}
		
		for(int i=0; i<M; i++) {
			int S = sc.nextInt();
			int E = sc.nextInt();
			A[S].add(E);
			A[E].add(S);
		}
		
		for(int i=1; i<=N; i++) { 
			Collections.sort(A[i]); // 각 노드의 인접노드 오름차순 정렬 Collection sort
		}
		
		visited = new boolean[N+1]; 
		DFS(Start);
		System.out.println();
		visited = new boolean[N+1];
		BFS(Start);
		System.out.println();
	}
	
	public static void DFS(int Node) { //
		System.out.print(Node+ " ");
		visited[Node] = true; 
		
		for(int i : A[Node]) {
			if(!visited[i]) { // 방문하지 않았을 경우
				DFS(i); // 재귀호출 = (호출스택에 해당 노드를 쌓는다)
			}
		}
	}
	
	private static void BFS(int Node) { // BFS 구현하기
	 
        /* 1. 각 노드를 먼저 배열에 Push한다
           2. 해당 노드를 방문처리한 후, 인접 노드를 Queue에 삽입한다.
            */
            
        Queue<Integer> q = new LinkedList<Integer>(); // 연결리스트 큐 구현
		q.add(Node); 
		visited[Node] = true;
		

		while(!q.isEmpty()) { 
			int now_Node = q.poll(); 
			System.out.print(now_Node + " ");
			for(int i : A[now_Node]) {
				if(!visited[i]) {
					visited[i]= true;
					q.add(i);
				}
				
			}
		}
	}
}