JAVA 백준 1260 DFS와 BFS (그래프)

 

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

---

문제

1. 첫째 줄부터 정점의 개수 N ( 1 <= N <= 1000 ), 간선의 개수 M ( 1 <= M <= 10000 ), 시작 정점의 번호 V가 공백으로 구분되어 주어진다.
2. 정점 번호는 1부터 N까지이며, 주어지는 간서는 모두 양방향이다.
3. 첫째 줄에는 DFS를 수행한 결과를 공백으로 구분하여 출력하고, 둘째 줄에는 BFS를 수행한 결과를 공백으로 구분하여 출력한다.

---

 

 

정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static int V; //정점 개수
    public static boolean[] visited;
    public static LinkedList<Integer>[] graph;
    public static StringBuilder sb;

    public static void dfs(int v) { //새로운 매개변수를 추가
        visited[v] = true;
        sb.append(v).append(" ");

        for (int nextV : graph[v]) {
            if (!visited[nextV]) {
                dfs(nextV); //매개변수로 들어갈 수 지정
            }
        }
    }

    public static void bfs(int v) { //새로운 매개변수를 추가
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(v);
        visited[v] = true;

        while (!queue.isEmpty()) {
            int num = queue.poll();
            sb.append(num).append(" ");
            for (int nextV : graph[num]) {
                if (!visited[nextV]) {
                    queue.offer(nextV);
                    visited[nextV] = true;
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        V = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int s = Integer.parseInt(st.nextToken());

        sb = new StringBuilder();

        graph = new LinkedList[V + 1];

        for (int i = 1; i < V + 1; i++) {
            graph[i] = new LinkedList<>();
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());

            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            graph[start].add(end);
            graph[end].add(start);
        }

        for (int i = 1; i < V + 1; i++) {
            Collections.sort(graph[i]);
        }

        visited = new boolean[V + 1];
        dfs(s);
        sb.append("\n");

        visited = new boolean[V + 1];
        bfs(s);

        System.out.println(sb);
    }
}

 

단순하게 DFS와 BFS 알고리즘을 이용하여 결과를 구해 출력하면 된다.