백준 1260번 - DFS와 BFS

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

1260번: DFS와 BFS

---

 

위 문제는 정점의 개수 N 간선의 개수 M 탐색을 시작하는 정점의 번호 V 를 입력받고

그 다음 줄에는 연결된 정점을 입력으로 받는다.

4 5 1
1 2
1 3
1 4
2 4
3 4

 

위 예제를 그림으로 나타내면 다음 그림처럼 정점과 간선이 연결되어 있는 형태로 나타난다.

 

 

 

 

▶코드

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

public class Main {
    static int edge_arr[][];
    static boolean visited_arr[];
    static int count;
    static int N;
    static int M;
    static int V;
    static Queue<Integer> q = new LinkedList<>();
    public static void BFS(int start){
        q.add(start);
        visited_arr[start]=true;
        System.out.print(start+" ");
        while(!q.isEmpty()){
            start = q.poll();
            for(int i=1;i<=N;i++){
                if(edge_arr[start][i]==1 && visited_arr[i]==false){
                    q.add(i);
                    visited_arr[i]=true;
                    System.out.print(i+" ");
                }
            }
        }
    }
    public static void DFS(int start){
        visited_arr[start]=true;
        System.out.print(start+ " ");
        if(count == N){
            return;
        }
        count++;
        for(int i=1;i<=N;i++){
            if(edge_arr[start][i]==1 && visited_arr[i]==false){
                DFS(i);
            }
        }
    }
    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());
        M = Integer.parseInt(st.nextToken());
        V = Integer.parseInt(st.nextToken());

        edge_arr = new int[1001][1001];
        visited_arr = new boolean[1001];

        for(int i=0;i<M;i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            edge_arr[a][b]=edge_arr[b][a]=1;
        }
        DFS(V);
        System.out.println();
        visited_arr = new boolean[1001];
        BFS(V);
    }
}