[Java] 백준 1260 DFS BFS

DFS (Depth First Search) 깊이 우선 탐색

인접해 있는 점 순으로 탐색해 나감 ( 재귀 사용 )

BFS (Breadth First Search) 너비 우선 탐색

가까운 정점 먼저 탐색 후 점차 한단계씩 탐색해 나감

문제 1260

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

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

DFS BFS 를 동시에 구현했습니다.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
  
public class Main {
      
    static int[][] graph;
    static boolean visited[];
    static int N;
    static int E;
    static int startPoint;
          
    public static void dfs(int i){
        visited[i] = true;
        System.out.print(i+" ");
          
        for(int j=1; j<=N; j++){
            if(graph[i][j]==1&& visited[j]==false){
                dfs(j);
            }
        }
    }
      
    public static void bfs(int i){
  
        Queue<Integer> q = new LinkedList<Integer>();
        q.offer(i);
        visited[i] = true;
        System.out.print(i+" ");
          
        int temp;
        while(!q.isEmpty()){
            temp = q.poll();
            for(int j=0; j<N+1; j++){
                if(graph[temp][j]==1&&visited[j]==false){
                    q.offer(j);
                    visited[j]=true;
                    System.out.print(j+" ");
                }
            }                       
        }
    }
      
    public static void main(String[] args) {
                  
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        graph = new int[1001][1001];
        E = sc.nextInt();
        visited = new boolean[10001];
        startPoint = sc.nextInt();
          
        int a,b;
          
        for(int i=1; i<=E; i++){
            a = sc.nextInt();
            b = sc.nextInt();
              
            graph[a][b] = graph[b][a] = 1;
        }
          
        dfs(startPoint);
          
        for(int j=1; j<=N; j++){
            visited[j]=false;
        }
        System.out.println();
          
        bfs(startPoint);
    }
}