[BOJ] 1260 DFS, BFS

문제

www.acmicpc.net/problem/1260

1260번: DFS와 BFS

 

풀이

import java.io.*;
import java.util.*;


public class Main {
	static boolean[][] graph;
	static boolean[] visited;
	static int result;
	
	static void bfs(int start,int N) {
		Queue<Integer> queue = new LinkedList<Integer>();
		StringBuilder sb = new StringBuilder();
		queue.add(start);
		visited[start] = true;
		while(!queue.isEmpty()) {
			int tmp = queue.poll();
			sb.append(tmp+" ");
			for(int i=1;i<=N;i++) {
				if(graph[tmp][i] && !visited[i]) {
					visited[i] = true;
					queue.add(i);
				}
			}
		}
		System.out.println(sb);
	}
	static void dfs_rec(int start, int N) {
		visited[start] = true;
		System.out.print(start+" ");
		for(int i=1;i<=N;i++) {
			if(graph[start][i] && !visited[i])
				dfs_rec(i,N);
		}
	}
	static void dfs_stack(int start, int N) {
		Stack<Integer> stack = new Stack<Integer>();
		int tmp = start;
		stack.push(start);
		visited[start] = true;
		System.out.print(start+" ");
		while(!stack.isEmpty()) {
			int num = stack.pop();
			for(int i=1;i<=N;i++) {
				if(graph[tmp][i] && !visited[i]) {
					tmp = i;
					visited[i] = true;
					stack.push(i);
					System.out.print(i+" ");
				}
			}
		}
		System.out.println();
	}
    public static void main(String[] args) throws IOException {
        //선언 및 입력
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st;
    	int N,M,V;
    	st = new StringTokenizer(br.readLine());
    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());
    	V = Integer.parseInt(st.nextToken());
    	
    	graph = new boolean[N+1][N+1];
    	visited  = new boolean[N+1];
    	for(int i=0;i<M;i++) {
    		st = new StringTokenizer(br.readLine());
    		int from,to;
    		from = Integer.parseInt(st.nextToken());
    		to = Integer.parseInt(st.nextToken());
    		graph[from][to] = graph[to][from] = true;
    	}
    	
    	
    	//dfs_stack(V,N);//스택 dfs
    	dfs_rec(V,N);//재귀 dfs
    	System.out.println();
    	Arrays.fill(visited, false);
    	bfs(V,N);
    }
}