백준 - DFS와 BFS[java]

문제출처: https://www.acmicpc.net/problem/1260

문제 설명

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력 예시

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

출력 예시

3 1 2 5 4
3 1 4 2 5

문제 풀이

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

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

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

        HashMap<Integer, ArrayList<Integer>> hm = new HashMap<>();
        HashSet<Integer> hs = new HashSet<>();
        StringBuilder sb = new StringBuilder();

        st.nextToken();
        int vertices = Integer.parseInt(st.nextToken());
        int startVertex = Integer.parseInt(st.nextToken());

        while (vertices-- > 0) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            ArrayList<Integer> connected = hm.containsKey(start) ? hm.get(start) : new ArrayList<>();
            connected.add(end);
            hm.put(start, connected);
            connected = hm.containsKey(end) ? hm.get(end) : new ArrayList<>();
            connected.add(start);
            hm.put(end, connected);
        }
        Queue<Integer> q = new LinkedList<>();
        q.add(startVertex);
        hs.add(startVertex);
        sb.append(startVertex).append(" ");
        BFS(q, hs, hm, sb);
        hs.clear();

        hs.add(startVertex);
        System.out.print(startVertex + " ");
        DFS(hm, startVertex, hs);
        System.out.println();

        System.out.println(sb);
        br.close();
        String i = "software engineering";

    }

    public static void DFS(HashMap<Integer, ArrayList<Integer>> hm, int startingVertex, HashSet<Integer> hs) {
        if (hm.get(startingVertex) != null) {
            for (int vertex : hm.get(startingVertex)) {
                if (!hs.contains(vertex)) {
                    hs.add(vertex);
                    System.out.print(vertex + " ");
                } else
                    continue;
                DFS(hm, vertex, hs);
            }
        }
    }

    public static void BFS(Queue<Integer> q, HashSet<Integer> hs, HashMap<Integer, ArrayList<Integer>> hm, StringBuilder sb) {
        while (!q.isEmpty()) {
            int vertex = q.poll();
            ArrayList<Integer> al = hm.get(vertex);
            if (al != null) {
                Collections.sort(al);
                for (int v : al) {
                    if (!hs.contains(v)) {
                        hs.add(v);
                        q.add(v);
                        sb.append(v).append(" ");
                    }
                }
            }
        }
    }
}

입력값을 받아서 HashMap<Integer, ArrayList> 형태로 그래프를 생성하였다.

DFS는 재귀 함수를 사용하였고, BFS는 큐를 사용하여 풀었다.

방문한 노드는 해쉬셋을 사용하여 확인을 하였다.