BFSとDFS

グラフィック表示
HashMap
新しいデータ構造に遭遇したら、まずCRUD(作成、読み取り、更新、削除)を理解しましょう.

// HashMap
        // 1. 생성 및 추가
        HashMap<String, Integer> testMap1 = new HashMap<>();
        HashMap<String, Integer> testMap2 = new HashMap<>(testMap1);
        HashMap<String, Integer> testMap3 = new HashMap<>(10); // 개수 제한
        HashMap<String, ArrayList<Integer>> testMap4 = new HashMap<>();
        testMap1.put("A", 1); // 추가
        testMap1.put("B", 2);
        // 2. 읽기
        System.out.println(testMap1);
        System.out.println(testMap1.get("A"));
        // 3. 갱신
        testMap1.put("A", 3);
        System.out.println(testMap1);
        // 4. 삭제
        testMap1.remove("A");
        System.out.println(testMap1);

        // HashMap으로 그래프 표현하기
        HashMap<String, ArrayList<String>> graph = new HashMap();
        graph.put("A", new ArrayList<String>(Arrays.asList("B", "C")));
        graph.put("B", new ArrayList<String>(Arrays.asList("A", "D")));
        graph.put("C", new ArrayList<String>(Arrays.asList("A", "G", "H", "I")));
        graph.put("D", new ArrayList<String>(Arrays.asList("B", "E", "F")));
        graph.put("E", new ArrayList<String>(Arrays.asList("D")));
        graph.put("F", new ArrayList<String>(Arrays.asList("D")));
        graph.put("G", new ArrayList<String>(Arrays.asList("C")));
        graph.put("H", new ArrayList<String>(Arrays.asList("C")));
        graph.put("I", new ArrayList<String>(Arrays.asList("C", "J")));
        graph.put("J", new ArrayList<String>(Arrays.asList("I")));

BFS(幅優先ナビゲーション)

import java.util.ArrayList;
import java.util.HashMap;

public class BFS {
    public ArrayList<String> searchFunc(HashMap<String, ArrayList<String>> graph, String source) {
        // 2개의 큐 필요
        ArrayList<String> visited = new ArrayList<>();
        ArrayList<String> queue = new ArrayList<>();

        // 출발점
        queue.add(source);

        while(queue.size() > 0) {
            String node = queue.remove(0);

            if (!visited.contains(node)) {
                visited.add(node);
                queue.addAll(graph.get(node));
            }
        }

        return visited;
    }
}

// 시간 복잡도는 O(V + E)

DFS(深度優先ナビゲーション)

import java.util.ArrayList;
import java.util.HashMap;

public class DFS {
    public ArrayList<String> searchFunc(HashMap<String, ArrayList<String>> graph, String source) {
        // 스택 1개, 큐 1개
        ArrayList<String> visited = new ArrayList<>();
        ArrayList<String> stack = new ArrayList<>();

        stack.add(source);

        while (stack.size() > 0) {
            String node = stack.remove(stack.size() - 1);

            if(!visited.contains(node)) {
                visited.add(node);
                stack.addAll(graph.get(node));
            }
        }

        return visited;
    }
}