[알고리즘/백준] #1260 DFS와 BFS

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

package algorithm_lab.day13.q2;

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

public class BJ_1260 {
	
	static int[][] map;
	static int N,M,V;
	static StringBuilder sb;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		sb = new StringBuilder();
		
		N = sc.nextInt();
		M = sc.nextInt();
		V = sc.nextInt();
		
		map=new int[N+1][N+1];
		
		for(int i=0;i<M;i++) {
			int from = sc.nextInt();
			int to = sc.nextInt();
			map[from][to] = map[to][from] = 1;
		}
		
		dfs(map,new boolean[N+1],V);
		sb.append("\n");
		bfs(map,V);
		sb.append("\n");
		
		System.out.print(sb.toString());
		
	}
	
	public static void bfs(int[][] map, int start) {
		Queue<Integer> queue = new LinkedList<Integer>();
		boolean[] visited = new boolean[N+1];
		
		queue.offer(start);
		visited[start]=true;
		
		while(!queue.isEmpty()) {
			int current = queue.poll();
			sb.append(current+" ");
			
			for(int i=1;i<=N;i++) {
				if(!visited[i] && map[current][i]!=0) {
					queue.offer(i);
					visited[i]=true;
				}
			}
		}
	}
	
	public static void dfs(int[][] map,boolean[] visited,int start) {
		visited[start] = true;
		sb.append(start+" ");
		
		for(int i=1;i<=N;i++) {
			if(!visited[i]&&map[start][i]!=0) {
				dfs(map,visited,i);
			}
		}
	}
}