[알고리즘]그래프 알고리즘🌟🤔

반응형

그래프 알고리즘은 복잡한 네트워크나 경로 문제를 해결하는 데 없어서는 안 될 필수 도구예요! 🚀 이번에는 그래프 탐색부터 최단 경로, 최소 신장 트리, 위상 정렬, 강결합 컴포넌트까지 하나씩 찬찬히 살펴보아요! 🌟

---

1. DFS와 BFS

그래프를 탐색할 때 사용하는 대표적인 방법 두 가지! 바로 DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)입니다. 🤔 그 차이를 알아볼까요?

1.1 DFS (깊이 우선 탐색)

• 원리: 이름 그대로 "깊이"를 먼저 탐색해요. 한쪽으로 끝까지 파고들다가 막히면 돌아옵니다.
• 특징: 재귀적으로 호출하거나 스택으로 구현합니다.
• 활용: 경로 찾기, 퍼즐 풀이 등 깊이 중심의 문제 해결! 🌱

public void dfs(Node node, Set<Node> visited) {
    if (visited.contains(node)) return;
    visited.add(node);
    System.out.println(node.value);
    for (Node neighbor : node.neighbors) {
        dfs(neighbor, visited);
    }
}

1.2 BFS (너비 우선 탐색)

• 원리: "너비"를 기준으로, 같은 레벨에 있는 노드를 차례로 탐색합니다.
• 특징: 큐를 사용해서 구현합니다.
• 활용: 최단 경로 찾기, 레벨 기반 탐색에 적합! 🚶‍♀️

public void bfs(Node start) {
    Queue<Node> queue = new LinkedList<>();
    Set<Node> visited = new HashSet<>();
    queue.add(start);
    visited.add(start);
    while (!queue.isEmpty()) {
        Node node = queue.poll();
        System.out.println(node.value);
        for (Node neighbor : node.neighbors) {
            if (!visited.contains(neighbor)) {
                queue.add(neighbor);
                visited.add(neighbor);
            }
        }
    }
}

---

2. 최단 경로 알고리즘

최단 경로를 찾는 건 그래프 문제에서 흔한 주제입니다. 🛤️ 여기선 대표적인 세 가지 알고리즘을 알아볼게요!

2.1 다익스트라 알고리즘

• 원리: 특정 시작점에서 다른 모든 노드까지의 최단 거리를 계산합니다.
• 특징: 가중치가 음수면 사용 불가. 힙을 사용하면 더 빠릅니다!
• 시간 복잡도: O(V + E log V)

public void dijkstra(Graph graph, Node start) {
    PriorityQueue<Node> pq = new PriorityQueue<>();
    Map<Node, Integer> distances = new HashMap<>();
    for (Node node : graph.nodes) {
        distances.put(node, Integer.MAX_VALUE);
    }
    distances.put(start, 0);
    pq.add(start);

    while (!pq.isEmpty()) {
        Node current = pq.poll();
        for (Edge edge : current.edges) {
            Node neighbor = edge.to;
            int newDist = distances.get(current) + edge.weight;
            if (newDist < distances.get(neighbor)) {
                distances.put(neighbor, newDist);
                pq.add(neighbor);
            }
        }
    }
}

2.2 벨만-포드 알고리즘

• 원리: 모든 간선을 반복적으로 확인하며 최단 경로를 갱신합니다.
• 특징: 음수 가중치도 처리 가능!
• 시간 복잡도: O(V * E)

public boolean bellmanFord(Graph graph, Node start) {
    Map<Node, Integer> distances = new HashMap<>();
    for (Node node : graph.nodes) {
        distances.put(node, Integer.MAX_VALUE);
    }
    distances.put(start, 0);

    for (int i = 0; i < graph.nodes.size() - 1; i++) {
        for (Edge edge : graph.edges) {
            Node u = edge.from;
            Node v = edge.to;
            int weight = edge.weight;
            if (distances.get(u) != Integer.MAX_VALUE && distances.get(u) + weight < distances.get(v)) {
                distances.put(v, distances.get(u) + weight);
            }
        }
    }

    for (Edge edge : graph.edges) {
        Node u = edge.from;
        Node v = edge.to;
        int weight = edge.weight;
        if (distances.get(u) != Integer.MAX_VALUE && distances.get(u) + weight < distances.get(v)) {
            return false; // 음수 사이클 존재
        }
    }
    return true;
}

2.3 플로이드-워셜 알고리즘

• 원리: 모든 노드 쌍 간의 최단 경로를 계산합니다.
• 특징: 동적 계획법 기반으로, 2차원 배열을 활용합니다.
• 시간 복잡도: O(V³)

public void floydWarshall(int[][] graph) {
    int V = graph.length;
    int[][] dist = new int[V][V];

    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            dist[i][j] = graph[i][j];
        }
    }

    for (int k = 0; k < V; k++) {
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
}

---

3. 최소 신장 트리 (MST)

모든 노드를 연결하는 최소 비용의 간선 집합을 찾는 문제입니다. 🌳

3.1 크루스칼 알고리즘

• 원리: 간선을 가중치 오름차순으로 정렬 후, 사이클을 생성하지 않는 간선만 선택합니다.
• 특징: 유니온-파인드(Union-Find)를 활용해 사이클을 검사합니다.
• 시간 복잡도: O(E log E)

public int kruskal(Graph graph) {
    List<Edge> edges = new ArrayList<>(graph.edges);
    edges.sort(Comparator.comparingInt(edge -> edge.weight));
    UnionFind uf = new UnionFind(graph.nodes.size());
    int mstWeight = 0;

    for (Edge edge : edges) {
        if (uf.union(edge.from.id, edge.to.id)) {
            mstWeight += edge.weight;
        }
    }
    return mstWeight;
}

3.2 프림 알고리즘

• 원리: 하나의 시작 노드에서 연결된 최소 가중치 간선을 선택하며 트리를 확장합니다.
• 특징: 힙을 사용하면 효율성이 높아집니다.
• 시간 복잡도: O(E log V)

public int prim(Graph graph) {
    PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparingInt(edge -> edge.weight));
    Set<Node> visited = new HashSet<>();
    int mstWeight = 0;

    Node start = graph.nodes.get(0);
    visited.add(start);
    pq.addAll(start.edges);

    while (!pq.isEmpty()) {
        Edge edge = pq.poll();
        if (!visited.contains(edge.to)) {
            visited.add(edge.to);
            mstWeight += edge.weight;
            pq.addAll(edge.to.edges);
        }
    }
    return mstWeight;
}

---

4. 위상 정렬

의존성이 있는 작업들을 순서대로 정리하려면 위상 정렬이 필요합니다! 📈

• 원리: 진입 차수가 0인 노드부터 처리하며 정렬을 완성합니다.
• 활용: 작업 스케줄링, 의존성 그래프 등.

public List<Node> topologicalSort(Graph graph) {
    List<Node> order = new ArrayList<>();
    Queue<Node> queue = new LinkedList<>();
    Map<Node, Integer> inDegree = new HashMap<>();

    for (Node node : graph.nodes) {
        inDegree.put(node, 0);
    }
    for (Node node : graph.nodes) {
        for (Node neighbor : node.neighbors) {
            inDegree.put(neighbor, inDegree.get(neighbor) + 1);
        }
    }

    for (Node node : inDegree.keySet()) {
        if (inDegree.get(node) == 0) {
            queue.add(node);
        }
    }

    while (!queue.isEmpty()) {
        Node current = queue.poll();
        order.add(current);
        for (Node neighbor : current.neighbors) {
            inDegree.put(neighbor, inDegree.get(neighbor) - 1);
            if (inDegree.get(neighbor) == 0) {
                queue.add(neighbor);
            }
        }
    }

    return order;
}

---

5. 강결합 컴포넌트 (SCC)

강결합 컴포넌트는 방향 그래프에서 서로 강하게 연결된 노드들의 집합을 뜻해요. 🎯

5.1 코사라주 알고리즘

• 원리: 그래프를 뒤집은 후, 두 번의 DFS로 SCC를 찾습니다.
• 특징: 간단한 구현으로도 정확한 결과를 얻을 수 있습니다.

import java.util.*;

public class KosarajuSCC {
    private int vertices;
    private List<List<Integer>> adjList = new ArrayList<>();
    private List<List<Integer>> reversedList = new ArrayList<>();
    private boolean[] visited;

    public KosarajuSCC(int vertices) {
        this.vertices = vertices;
        for (int i = 0; i < vertices; i++) {
            adjList.add(new ArrayList<>());
            reversedList.add(new ArrayList<>());
        }
        visited = new boolean[vertices];
    }

    public void addEdge(int from, int to) {
        adjList.get(from).add(to);
        reversedList.get(to).add(from);
    }

    private void dfs(int node, Stack<Integer> stack) {
        visited[node] = true;
        for (int neighbor : adjList.get(node)) {
            if (!visited[neighbor]) {
                dfs(neighbor, stack);
            }
        }
        stack.push(node);
    }

    private void dfsReversed(int node, List<Integer> scc) {
        visited[node] = true;
        scc.add(node);
        for (int neighbor : reversedList.get(node)) {
            if (!visited[neighbor]) {
                dfsReversed(neighbor, scc);
            }
        }
    }

    public List<List<Integer>> findSCCs() {
        Stack<Integer> stack = new Stack<>();
        Arrays.fill(visited, false);

        // Step 1: Perform DFS and fill the stack
        for (int i = 0; i < vertices; i++) {
            if (!visited[i]) {
                dfs(i, stack);
            }
        }

        // Step 2: Reverse DFS on the reversed graph
        Arrays.fill(visited, false);
        List<List<Integer>> sccList = new ArrayList<>();
        while (!stack.isEmpty()) {
            int node = stack.pop();
            if (!visited[node]) {
                List<Integer> scc = new ArrayList<>();
                dfsReversed(node, scc);
                sccList.add(scc);
            }
        }

        return sccList;
    }

    public static void main(String[] args) {
        KosarajuSCC graph = new KosarajuSCC(5);
        graph.addEdge(0, 1);
        graph.addEdge(1, 2);
        graph.addEdge(2, 0);
        graph.addEdge(1, 3);
        graph.addEdge(3, 4);

        List<List<Integer>> sccs = graph.findSCCs();
        System.out.println("Strongly Connected Components:");
        for (List<Integer> scc : sccs) {
            System.out.println(scc);
        }
    }
}

5.2 타잔 알고리즘

• 원리: DFS 방문 순서와 Low-Link 값을 이용해 SCC를 탐색합니다.
• 특징: 단일 DFS로 효율적인 SCC 탐색이 가능!
• 시간 복잡도: O(V + E)

import java.util.*;

public class TarjanSCC {
    private int vertices;
    private List<List<Integer>> adjList = new ArrayList<>();
    private int[] ids, low;
    private boolean[] onStack;
    private Stack<Integer> stack;
    private int id = 0;
    private List<List<Integer>> sccList = new ArrayList<>();

    public TarjanSCC(int vertices) {
        this.vertices = vertices;
        for (int i = 0; i < vertices; i++) {
            adjList.add(new ArrayList<>());
        }
        ids = new int[vertices];
        low = new int[vertices];
        onStack = new boolean[vertices];
        stack = new Stack<>();
        Arrays.fill(ids, -1);
    }

    public void addEdge(int from, int to) {
        adjList.get(from).add(to);
    }

    private void dfs(int at) {
        stack.push(at);
        onStack[at] = true;
        ids[at] = low[at] = id++;

        for (int to : adjList.get(at)) {
            if (ids[to] == -1) {
                dfs(to);
                low[at] = Math.min(low[at], low[to]);
            } else if (onStack[to]) {
                low[at] = Math.min(low[at], ids[to]);
            }
        }

        // On root node, start SCC
        if (ids[at] == low[at]) {
            List<Integer> scc = new ArrayList<>();
            while (true) {
                int node = stack.pop();
                onStack[node] = false;
                scc.add(node);
                if (node == at) break;
            }
            sccList.add(scc);
        }
    }

    public List<List<Integer>> findSCCs() {
        for (int i = 0; i < vertices; i++) {
            if (ids[i] == -1) {
                dfs(i);
            }
        }
        return sccList;
    }

    public static void main(String[] args) {
        TarjanSCC graph = new TarjanSCC(5);
        graph.addEdge(0, 1);
        graph.addEdge(1, 2);
        graph.addEdge(2, 0);
        graph.addEdge(1, 3);
        graph.addEdge(3, 4);

        List<List<Integer>> sccs = graph.findSCCs();
        System.out.println("Strongly Connected Components:");
        for (List<Integer> scc : sccs) {
            System.out.println(scc);
        }
    }
}

---

결론

그래프 알고리즘은 알고 보면 그렇게 어렵지 않아요! 💡 차근차근 개념을 이해하고, 코드를 따라 작성하다 보면 자신감이 붙을 거예요. 😊 DFS, BFS, MST, 위상 정렬은 코딩 테스트와 실무에서 정말 많이 쓰이니 꼭 익혀두세요! 🙌