[백준] 1260 DFS와 BFS

문제보기

import java.util.*;

public class Main
{
  public static ArrayList<Integer>[] a; //인접리스트
  public static boolean[] check; // 방문여부 저장

  public static void dfs(int x){ //dfs는 재귀 방식
	 	// 방문한 적이 있다면 종료
    if(check[x] == true ){
      return;
    }
		// 아니라면 지금 방문한거니까 방문 체크
    check[x] = true;
    // 방문해서 해야할 일을 해줍니다
    System.out.print(x + " ");
		
    // 인접리스트 중에 갈 수 있는 곳이 있다면 방문하자
    for(int y: a[x]){
      if(check[y] == false){
        dfs(y);
      }
    }
  }

  public static void bfs(int start){ // bfs는 큐를 이용한다
    Queue<Integer> q = new LinkedList<Integer>(); // 큐 선언
    q.add(start); // 시작값 넣기
    check[start] = true; // 방문 체크
	
    // 여기가 bfs의 핵심이다 
    while(!q.isEmpty()){
      // 1. 일단 큐에서 제일 오래된 오브젝트를 꺼내준다 
      int x = q.remove();
      
      // 2. 걔로 할 일이 있다면 해주자 
      System.out.print(x + " ");
      
      // 3. 인접리스트 중에 갈 수 있는 곳이 있다면 큐에 추가해주자
      for(int y:a[x]){
        if(check[y] == false){
          check[y] = true;
          q.add(y);
        }
      }
    }
  }

  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 = (ArrayList<Integer>[]) new ArrayList[n+1]; //node starts from 1
    for(int i = 0 ; i <= n ; i++){
      a[i] = new ArrayList<Integer>(); // insert empty ArrayList
    }

    for(int i = 0 ; i < m ; i++ ){ //get info about edges from test case 
      int u = sc.nextInt();
      int v = sc.nextInt();
      a[u].add(v);
      a[v].add(u);
    }

    for(int i = 0 ; i <= n ; i++ ){ //sorting arraylist 
      Collections.sort(a[i]);
    }

    check = new boolean[n+1]; //initialization 
    dfs(start);
    System.out.println();

    check = new boolean[n+1]; //initialization 
    bfs(start);
    System.out.println();
  }
}