[TIL][02.21] 그래프, 트리, BFS, DFS, 스택, 큐

복습

• binary tree : 각 노드가 최대 2개의 자식노드를 가질 수 있는 트리
• ternary tree : 각 노드가 최대 3개의 자식노드를 가질 수 있는 트리
• skewed binary tree : 모든 노드가 한쪽 방향으로만 연결된 트리
• binary search tree : 왼쪽 자식은 부모보다 작은 값, 오른쪽 자식은 부모보다 큰 값을 가짐
• complete binary tree : 왼쪽부터 차례대로 노드가 채워진 트리
• full binary tree : 모든 노드가 0개 또는 2개의 자식을 가짐
• perfect binary tree : 모든 리프 노드가 같은 높이, 모든 내부 노드가 2개의 자식을 가짐. 꽉 찬 모양

 

• 그래프 : 정점과 간선으로 이루어진 자료구조
• 트리 : 사이클이 없는 그래프 (그래프의 부분 집합)
• 그래프 탐색 방식 : DFS, BFS
• 데이터 처리 방식 : 인접행렬, 인접리스트
• 인접행렬은 완전탐색. 전체를 탐색해야함.
• 인접리스트는 필요한 부분만 탐색가능

그래프 응용

최단경로

가중치가 없는 그래프에서 특정 두 노드 간의 거리를 최소화하는 것 => BFS가 최고 (ex. 미로찾기)

BFS는 가까운 노드부터 탐색하므로 가중치가 없을 때 최단 경로를 보장함

배열 사용 : 노드가 정수 형태 일 때 (ex. 1차원 이동)

정점 class 사용 : 노드에 추가적인 정보가 필요할 때(ex. 좌표 이동 문제)

import java.util.*;

public class BFS {
    public static List<Integer> bfs(List<List<Integer>> graph, int start) {
        boolean[] visited = new boolean[graph.size()];
        Queue<Integer> queue = new LinkedList<>();
        List<Integer> result = new ArrayList<>();
        
        queue.offer(start);
        visited[start] = true;
        
        while (!queue.isEmpty()) {
            int node = queue.poll();
            result.add(node);
            
            for (int neighbor : graph.get(node)) {
                if (!visited[neighbor]) {
                    queue.offer(neighbor);
                    visited[neighbor] = true;
                }
            }
        }
        
        return result;
    }

    public static void main(String[] args) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < 5; i++) {
            graph.add(new ArrayList<>());
        }

        graph.get(0).add(1);
        graph.get(0).add(2);
        graph.get(1).add(3);
        graph.get(2).add(4);

        List<Integer> result = bfs(graph, 0);
        
        System.out.println(result);
    }
}

 

• 시작 노드를 큐에 넣고 탐색을 시작
• 큐에서 첫 번째 노드를 꺼내고, 그 노드의 인접 노드들을 큐에 넣음
• 계속 큐에서 노드를 꺼내며 탐색하고, 새로운 노드를 큐에 넣는 과정을 반복
• 큐가 비면, 모든 노드를 탐색한 후 결과 배열을 반환

과제

백준 1697

[JAVA]백준 - 1697번 숨바꼭질 (실버1)

도전 문제 4 : 2805-D3 농작물 수확하기

[JAVA]SWEA - 2805 농작물 수확하기 (D3)

도전 문제 5 : 1208 [S/W 문제해결 기본] 1일차 - Flatten

[JAVA]SWEA - 1208 Flatten (D3)

도전 문제 6 : 2001-D2 파리 퇴치

[JAVA]SWEA - 2001 파리 퇴치 (D2)

프로그래머스 Lv.2 (1)

[JS]프로그래머스 - 최솟값 만들기 (Lv.2)

프로그래머스 Lv.2 (2)

[JS]프로그래머스 - 점프와 순간이동 (Lv.2)

프로그래머스 Lv.2 (3)

[JS]프로그래머스 - 프로세스 (Lv.2)

프로그래머스 Lv.2 (4)

[JS]프로그래머스 - 기능개발 (Lv.2)