[Baekjoon Online Judge] 1260번: DFS와 BFS

hyeonic 2021. 1. 12. 22:32

1260번: DFS와 BFS

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사

www.acmicpc.net

[그래프 탐색] DFS와 BFS

1. 그래프란? 그래프는 vertex(정점)와 vertex(정점)를 이어주는 edge(간선)로 이루어져 있다. 정점은 대상이나 개체를 나타내고, 간선은 이들 간의 관계를 나타낸다. 상호 관계가 대칭적이지 않은

hyeonic.tistory.com

간선을 연결하는 두 정점의 번호를 입력 받아 그래프를 그리고 DFS와 BFS로 탐색한다. DFS와 BFS에 대한 설명은 https://hyeonic.tistory.com/54에서 확인해볼 수 있다.

DFS는 재귀를 활용하여 작성하였고, BFS의 경우 Queue를 활용하여 작성하였다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;

public class Baekjoon1260 {

    static BufferedReader bufferedReader;
    static BufferedWriter bufferedWriter;
    static int[][] graph;
    static boolean[] visited;
    static int n, m, v;

    public static void bfs(int start) throws IOException {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        visited[start] = true;
        while (!queue.isEmpty()) {
            int vertex = queue.poll();
            bufferedWriter.write(vertex + " ");

            for (int i = 0; i < n + 1; i++) {
                if (graph[vertex][i] == 1 && !visited[i]) {
                    queue.offer(i);
                    visited[i] = true;
                }
            }
        }
    }

    public static void dfs(int start) throws IOException {
        visited[start] = true;
        bufferedWriter.write(start + " ");
        for (int i = 1; i < n + 1; i++) {
            if (graph[start][i] == 1 && !visited[i]) dfs(i);
        }
    }

    public static void main(String[] args) throws IOException {

        bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] input = bufferedReader.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        m = Integer.parseInt(input[1]);
        v = Integer.parseInt(input[2]);

        graph = new int[n + 1][n + 1];
        visited = new boolean[n + 1];

        for (int i = 0; i < m; i++) {
            String[] vertices = bufferedReader.readLine().split(" ");
            int x = Integer.parseInt(vertices[0]);
            int y = Integer.parseInt(vertices[1]);

            graph[x][y] = 1;
            graph[y][x] = 1;
        }

        dfs(v);
        bufferedWriter.write("\n");
        visited = new boolean[n + 1];
        bfs(v);

        bufferedWriter.flush();
        bufferedReader.close();
        bufferedWriter.close();
    }
}