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

 

 

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

1260번: DFS와 BFS

 

 

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

public class Solution {
	
	static int[][] arr;
	
	static int N;
	
	static StringBuilder sb;

	public static void main(String[] args){
		
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		
		int M = sc.nextInt();
		
		int V = sc.nextInt();
		
		arr = new int[N][N];
		
		for(int i=0; i<M; i++) {
			int from = sc.nextInt()-1;
			int to = sc.nextInt()-1;
			arr[from][to] = arr[to][from] = 1;
		}
		
		sb = new StringBuilder();
		DFS(arr, new boolean[N], V-1);
		System.out.println(sb.toString());
		BFS(arr, V-1);
		System.out.println(sb.toString());
		
	}
	
	static void BFS(int[][] arr, int start) {
		
		sb = new StringBuilder();
		
		Queue<Integer> queue = new LinkedList<>();
		
		boolean[] check = new boolean[N];
		
		queue.offer(start);
		check[start] = true;
		
		while(!queue.isEmpty()) {
			
			int cur = queue.poll();
			
			sb.append(cur+1).append(" ");
			
			for(int i=0; i<N; i++) {
				if(!check[i] && arr[cur][i]!=0) {
					queue.offer(i);
					check[i] = true;
				}
			}
		}
		
	}
	
	static void DFS(int[][] arr, boolean[] check, int cur) {
		
		sb.append(cur+1).append(" ");
		check[cur] = true;
		
		for(int i=0; i<N; i++) {
			if(!check[i] && arr[cur][i] !=0) {
				DFS(arr, check, i);
			}
		}
		
	}
  
}