트리 bfs 구현 템플릿

클래스구현

일반 트리

class Node {
    int value;
    List<Node> children = new ArrayList<>();

    Node(int value) {
        this.value = value;
    }
}

void bfs(Node root) {
    if (root == null) return;

    Queue<Node> queue = new LinkedList<>();
    queue.add(root); // 루트 노드를 큐에 삽입

    while (!queue.isEmpty()) {
        Node curNode = queue.remove(); // 큐에서 노드를 꺼냄

        // 자식 노드들을 큐에 삽입
        for (Node child : curNode.children) {
            queue.add(child);
        }
    }
}

 

이진 트리

class Node {
    int value;
    Node left;
    Node right;

    Node(int value) {
        this.value = value;
    }
}

void bfs(Node root) {
    if (root == null) return;

    Queue<Node> queue = new LinkedList<>();
    queue.add(root); // 루트 노드를 큐에 삽입

    while (!queue.isEmpty()) {
        Node curNode = queue.remove(); // 큐에서 노드를 꺼냄

        // 왼쪽 자식이 있으면 큐에 넣음
        if (curNode.left != null) {
            queue.add(curNode.left);
        }
        // 오른쪽 자식이 있으면 큐에 넣음
        if (curNode.right != null) {
            queue.add(curNode.right);
        }
    }
}

인접리스트 구현

일방향 트리

visited를 안써도 문제 없지만 visited를 쓰는 형태를 기본으로..

Map<Integer, List<Integer>> tree = new HashMap<>() {{
    put(1, List.of(2, 3));
    put(2, List.of(4, 5));
    put(3, List.of());
    put(4, List.of());
    put(5, List.of());
}};

void bfs(int start, Map<Integer, List<Integer>> tree) {
    Set<Integer> visited = new HashSet<>();
    Queue<Integer> queue = new LinkedList<>();

    queue.add(start);
    visited.add(start);

    while (!queue.isEmpty()) {
        int cur = queue.remove();

        // 현재 노드에서 갈 수 있는 (자식) 노드 확인
        for (int nxt : tree.get(cur)) {
            if (!visited.contains(nxt)) {
                visited.add(nxt);
                queue.add(nxt);
            }
        }
    }
}

 

양방향 트리

Map<Integer, List<Integer>> tree = new HashMap<>() {{
    put(1, List.of(2, 3));
    put(2, List.of(1, 4, 5));
    put(3, List.of(1));
    put(4, List.of(2));
    put(5, List.of(2));
}};

void bfs(int start, Map<Integer, List<Integer>> tree) {
    // 시작 노드를 방문 처리하고 큐에 추가
    Set<Integer> visited = new HashSet<>();
    visited.add(start);

    Queue<Integer> queue = new LinkedList<>();
    queue.add(start);

    while (!queue.isEmpty()) {
        int cur = queue.remove();

        // 양방향 연결이므로, 이미 방문한 노드는 다시 방문하지 않도록 체크
        for (int nxt : tree.getOrDefault(cur, List.of())) {
            if (!visited.contains(nxt)) {
                visited.add(nxt);
                queue.add(nxt);
            }
        }
    }
}