[백준(Baekjoon)][자바(java)] 1260 : DFS와 BFS / DFS와 BFS

 

www.acmicpc.net/problem/1260

1260번: DFS와 BFS

 

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

public class Main {
	
	static int n, edge[][];
	static boolean visited[];
	static StringBuilder sb = new StringBuilder();
	
	public static void DFS( int s ) {	// 스택 이용
		Stack<Integer> stack = new Stack<>();
		visited = new boolean[n+1];
		stack.add( s );
		while( !stack.empty() ) {
			int v = stack.pop();
			if( visited[v] )  continue;
			else  visited[v] = true;
			sb.append( v + " " );
			for( int u = n; u >= 1; u-- ) 	// 정점 번호가 작은 것을 먼저 방문해야 함을 고려 ( 스택의 후입 선출 특성 )
				if( edge[v][u] == 1 && !visited[u] ) 
					stack.add( u );	
		}
	}
	
	public static void BFS( int s ) {	// 큐 이용
		Deque<Integer> queue = new ArrayDeque<>();
		visited = new boolean[n+1];
		queue.add( s );
		while( !queue.isEmpty() ) {
			int v = queue.remove();
			if( visited[v] )  continue;
			else  visited[v] = true;
			sb.append( v + " " );
			for( int u = 1; u <= n; u++ )
				if( edge[v][u] == 1 && !visited[u] ) 	
					queue.add( u );
		}
	}

	public static void main(String[] args) throws IOException {
		
        // 값 입력 받음
		BufferedReader br = new BufferedReader( new InputStreamReader(System.in) );
		StringTokenizer st = new StringTokenizer( br.readLine() );
		n = Integer.parseInt( st.nextToken() );
		int m = Integer.parseInt( st.nextToken() );
		int v = Integer.parseInt( st.nextToken() ), i, j;
		int c[][] = new int[m][2];
		for( i = 0; i < m; i++ ) {
			st = new StringTokenizer( br.readLine() );
			for( j = 0; j < 2; j++ )
				c[i][j] = Integer.parseInt( st.nextToken() );
		}
		br.close();
	
    	// 그래프 인접 행렬 만듦
		edge = new int[n+1][n+1];
		for( i = 0; i < m; i++ )
			edge[c[i][0]][c[i][1]] = 1;
		for( i = 0; i < m; i++ )
			edge[c[i][1]][c[i][0]] = 1;
		
        // DFS, BFS 그래프 탐색
		DFS( v );
		sb.append("\n");
		BFS( v );
		
		System.out.println( sb );
	}
}