[백준] DFS와 BFS (1260)

문제

www.acmicpc.net/problem/1260

1260번: DFS와 BFS

풀이

import java.util.Arrays;

import java.util.LinkedList;

import java.util.Queue;

import java.util.Scanner;

 

public class Main {

    private static int edge, vertex, start;

    private static int[][] graph;

    private static boolean[] check;

 

    public static void main(String[] args) {

        // 입력 받기

        Scanner sc = new Scanner(System.in);

 

        edge = sc.nextInt();

        vertex = sc.nextInt();

        start = sc.nextInt();

        // 행렬

        graph = new int[edge + 1][edge + 1];

        check = new boolean[edge + 1];

 

        for (int i = 0; i < vertex; i++) {

            int first = sc.nextInt();

            int second = sc.nextInt();

 

            graph[first][second] = 1;

            graph[second][first] = 1;

        }

 

        dfs(start);

        System.out.println();

        // 배열 전체초기화

        Arrays.fill(check, false);

        bfs(start);

    }

 

    public static void dfs(int start) {

        // 시작점 방문

        check[start] = true;

        System.out.print(start + " ");

        // 돌면서 체크

        for (int i = 1; i < edge + 1; i++) {

            if (graph[start][i] == 1 && !check[i])

                dfs(i);

        }

    }

 

    public static void bfs(int start) {

        Queue<Integer> q = new LinkedList<>();

        // 시작점을 큐에 넣고

        q.offer(start);

        // 방문했다고 저장

        check[start] = true;

 

        //  정점이 없어질때까지

        while (!q.isEmpty()) {

            //정점을 poll해서 이동

            int vertex = q.poll();

            System.out.print(vertex + " ");

 

            // 이동된 정점에서 연결된 점들을 큐에 넣고 방문했는지 체

            for (int i = 1; i < edge + 1; i++) {

                if (graph[vertex][i] == 1 && !check[i]) {

                    q.offer(i);

                    check[i] = true;

                }

            }

        }

    }

}