Java 자바 알고리즘 스택, 큐, 그래프, DFS, BFS 개념 정리

java

개발일지

알고리즘 문제를 풀면서 중요한 자료구조와 메소드들을 정리해가고 있습니다. 이러한 과정들을 통해 기존 지식을 되짚어보고 새로운 통찰력을 얻고 있습니다.

문제를 하나씩 해결해 가면서 제 실력이 점점 향상되고 있다는 것을 느끼고 있습니다. 하지만, 더욱 능력을 키우기 위해서는 다양한 문제들에 도전하는 것이 필요하다고 생각합니다. 이러한 목표를 달성하기 위해 지속적으로 문제를 풀고, 그 과정을 블로그에 기록할 예정입니다.

이번 글에서는 자바 알고리즘에서 자주 사용되는 스택, 큐, 그래프, DFS, BFS 에 대해 간략하게 정리해보려 합니다.

스택(Stack)

자바에서 스택(Stack)은 LIFO(Last In, First Out) 원리에 따라 작동하는 자료구조입니다. 이는 마지막에 추가된 요소가 가장 먼저 제거된다는 것을 의미합니다. 스택은 데이터의 삽입, 삭제, 탐색 등의 작업을 수행할 때 사용됩니다.

스택의 주요 연산

push: 스택의 맨 위에 요소를 추가합니다.
pop: 스택의 맨 위에 있는 요소를 제거하고 반환합니다.
peek: 스택의 맨 위에 있는 요소를 반환하지만, 제거하지는 않습니다.
isEmpty: 스택이 비어 있는지 여부를 확인합니다.

💡자바의 java.util.Stack 클래스를 사용하여 스택을 구현할 수 있습니다. 이 클래스는 위에서 언급한 모든 기능을 제공합니다.

스택 예제

스택을 사용하여 간단한 스택 작업을 수행하는 예제 코드입니다.

Java

import java.util.Stack;

public class StackExample {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();

        // 스택에 요소를 추가 (push)
        stack.push(1);
        stack.push(2);
        stack.push(3);

        System.out.println("Current stack: " + stack);

        // 가장 최근에 추가된 요소를 제거 (pop)
        int poppedElement = stack.pop();
        System.out.println("Popped element: " + poppedElement);

        System.out.println("Stack after pop: " + stack);

        // 스택의 맨 위 요소 확인 (peek)
        int topElement = stack.peek();
        System.out.println("Top element: " + topElement);

        // 스택이 비어 있는지 확인 (isEmpty)
        boolean isEmpty = stack.isEmpty();
        System.out.println("Is the stack empty? " + isEmpty);
    }
}

Java

이 코드에서는 java.util.Stack 클래스를 사용하여 Integer 타입의 스택을 만듭니다. 여기서는 push 메소드를 사용하여 스택에 요소를 추가하고, pop 메소드로 맨 위의 요소를 제거하며, peek 메소드로 맨 위의 요소를 확인합니다. 또한 isEmpty 메소드로 스택이 비어 있는지 확인합니다.

✔️스택은 다양한 애플리케이션에서 중요한 역할을 합니다. 예를 들어, 브라우저의 뒤로 가기 기능, 함수 호출의 스택 트레이스, 깊이 우선 탐색(DFS) 알고리즘 등에서 사용됩니다.

큐(Queue)

자바에서 큐(Queue)는 FIFO(First In, First Out) 원리에 따라 작동하는 자료구조입니다. 이는 처음에 추가된 요소가 가장 먼저 제거된다는 것을 의미합니다. 큐는 주로 데이터가 들어오는 순서대로 처리해야 할 때 사용됩니다.

큐의 주요 연산

offer/enqueue: 큐의 끝에 요소를 추가합니다.
poll/dequeue: 큐의 맨 앞에 있는 요소를 제거하고 반환합니다.
peek: 큐의 맨 앞에 있는 요소를 반환하지만, 제거하지는 않습니다.
isEmpty: 큐가 비어 있는지 여부를 확인합니다.

💡자바의 java.util.Queue 인터페이스와 java.util.LinkedList 클래스를 사용하여 큐를 구현할 수 있습니다. LinkedList 클래스는 Queue 인터페이스의 모든 기능을 구현합니다.

큐 예제

큐를 사용하여 간단한 큐 작업을 수행하는 예제 코드입니다.

Java

import java.util.LinkedList;
import java.util.Queue;

public class QueueExample {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();

        // 큐에 요소를 추가 (offer/enqueue)
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);

        System.out.println("Current queue: " + queue);

        // 큐의 맨 앞 요소를 제거 (poll/dequeue)
        int removedElement = queue.poll();
        System.out.println("Removed element: " + removedElement);

        System.out.println("Queue after poll: " + queue);

        // 큐의 맨 앞 요소 확인 (peek)
        int frontElement = queue.peek();
        System.out.println("Front element: " + frontElement);

        // 큐가 비어 있는지 확인 (isEmpty)
        boolean isEmpty = queue.isEmpty();
        System.out.println("Is the queue empty? " + isEmpty);
    }
}

Java

이 코드에서는 java.util.LinkedList 클래스를 사용하여 Integer 타입의 큐를 만듭니다. offer 메소드로 큐에 요소를 추가하고, poll 메소드로 맨 앞의 요소를 제거하며, peek 메소드로 맨 앞의 요소를 확인합니다. isEmpty 메소드는 큐가 비어 있는지 확인하는 데 사용됩니다.

✔️큐는 다양한 애플리케이션에서 사용됩니다. 예를 들어, 프린터 작업 대기열, 콜센터의 고객 대기열, 레벨 순서 탐색(BFS) 알고리즘 등에서 큐가 활용됩니다.

그래프(Graph)

자바에서 그래프를 구현하는 방법에는 여러 가지가 있습니다. 기본적으로 그래프는 노드(또는 정점)와 이들을 연결하는 간선의 집합으로 구성됩니다. 그래프는 크게 두 가지 유형으로 나뉘는데, 방향성이 있는 유향 그래프(Directed Graph)와 방향성이 없는 무향 그래프(Undirected Graph)입니다.

자바에서 그래프를 구현하는 가장 기본적인 방법은 인접 리스트(Adjacency List)와 인접 행렬(Adjacency Matrix)을 사용하는 것입니다.

인접 리스트 (Adjacency List)

인접 리스트는 각 노드에서 다른 노드로의 간선을 리스트로 나타냅니다. 이 방법은 간선의 수에 비례하는 메모리를 사용하기 때문에 간선이 적은 그래프에서 효율적입니다.

Java

import java.util.*;

class Graph {
    private Map<Integer, List<Integer>> adjList;

    public Graph(int vertices) {
        adjList = new HashMap<>();
        for (int i = 0; i < vertices; i++) {
            adjList.put(i, new LinkedList<>());
        }
    }

    void addEdge(int source, int dest) {
        adjList.get(source).add(dest);
        // 무향 그래프의 경우, 아래 줄도 추가합니다.
        // adjList.get(dest).add(source);
    }
}

Java

인접 행렬 (Adjacency Matrix)

인접 행렬은 2차원 배열을 사용하여 노드 간의 연결 관계를 나타냅니다. 이 방법은 모든 노드 쌍에 대한 정보를 저장하기 때문에 메모리 사용량이 더 많지만, 특정 노드 간 연결 여부를 빠르게 확인할 수 있습니다.

Java

class Graph {
    private boolean[][] adjMatrix;
    private int numVertices;

    public Graph(int numVertices) {
        this.numVertices = numVertices;
        adjMatrix = new boolean[numVertices][numVertices];
    }

    void addEdge(int i, int j) {
        adjMatrix[i][j] = true;
        // 무향 그래프의 경우, 아래 줄도 추가합니다.
        // adjMatrix[j][i] = true;
    }
}

Java

DFS BFS

DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)는 그래프 또는 트리를 탐색하는 두 가지 기본적인 알고리즘입니다. 각각의 알고리즘은 고유한 방식으로 그래프의 모든 정점을 방문합니다.

DFS BFS 차이점

DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)는 그래프를 탐색하는 두 가지 기본적인 방법입니다. 이들의 주요 차이점은 탐색하는 순서와 방식에 있습니다.

DFS (깊이 우선 탐색):
- DFS는 그래프의 깊은 부분을 먼저 탐색하는 방식입니다.
- 스택 또는 재귀 함수를 사용하여 구현됩니다.
- 시작 정점에서 한 방향으로 갈 수 있는 한 최대한 깊게 이동한 다음, 더 이상 갈 곳이 없으면 마지막 분기점(정점)으로 되돌아와 다른 경로를 탐색합니다.
- 모든 노드를 방문하는 것이 목표일 때 주로 사용됩니다.
BFS (너비 우선 탐색):
- BFS는 그래프의 넓은 부분을 먼저 탐색하는 방식입니다.
- 큐를 사용하여 구현됩니다.
- 시작 정점에 인접한 모든 정점을 먼저 방문하고, 이들에 인접한 정점들을 순차적으로 방문하는 방식으로 진행합니다.
- 최단 경로를 찾거나, 시작 정점으로부터 가까운 정점을 우선적으로 방문할 때 유용합니다.

요약하자면, DFS는 깊이를 우선으로 탐색하며 스택 또는 재귀를 사용하여 구현되고, BFS는 너비를 우선으로 탐색하며 큐를 사용하여 구현됩니다.

DFS (깊이 우선 탐색)

DFS는 그래프의 깊은 부분을 우선적으로 탐색하는 알고리즘입니다. DFS는 스택(또는 재귀 함수)을 사용하여 구현할 수 있으며, 시작 정점에서부터 깊이 들어가며 탐색한 후, 더 이상 탐색할 수 없게 되면 마지막으로 방문했던 정점으로 되돌아가서 다른 경로를 탐색합니다.

작동 방식

시작 정점을 스택에 삽입하고 방문 처리합니다.
스택의 최상단 정점에서 방문하지 않은 인접 정점을 찾아 방문하고 스택에 삽입합니다.
더 이상 방문할 인접 정점이 없으면 스택에서 정점을 제거(팝)합니다.
스택이 빌 때까지 2번과 3번을 반복합니다.

예제 코드

Java

import java.util.*;

public class Graph {
    private LinkedList<Integer>[] adj;

    public Graph(int v) {
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new LinkedList<>();
    }

    public void addEdge(int v, int w) {
        adj[v].add(w);
    }

    private void DFSUtil(int v, boolean[] visited) {
        visited[v] = true;
        System.out.print(v + " ");

        for (int n : adj[v]) {
            if (!visited[n])
                DFSUtil(n, visited);
        }
    }

    public void DFS(int v) {
        boolean[] visited = new boolean[adj.length];
        DFSUtil(v, visited);
    }
}

Java

BFS (너비 우선 탐색)

BFS는 그래프의 넓은 부분을 우선적으로 탐색하는 알고리즘입니다. BFS는 큐를 사용하여 구현하며, 시작 정점에서부터 가장 가까운 정점을 우선적으로 방문한 후, 점차적으로 더 멀리 있는 정점들을 방문합니다.

작동 방식

시작 정점을 큐에 삽입하고 방문 처리합니다.
큐에서 정점을 꺼내고 해당 정점의 모든 인접 정점을 확인합니다.
방문하지 않은 인접 정점을 큐에 삽입하고 방문 처리합니다.
큐가 빌 때까지 2번과 3번을 반복합니다.

예제 코드

Java

import java.util.*;

public class Graph {
    private LinkedList<Integer>[] adj;

    public Graph(int v) {
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new LinkedList<>();
    }

    public void addEdge(int v, int w) {
        adj[v].add(w);
    }

    public void BFS(int s) {
        boolean[] visited = new boolean[adj.length];
        LinkedList<Integer> queue = new LinkedList<>();

        visited[s] = true;
        queue.add(s);

        while (!queue.isEmpty()) {
            s = queue.poll();
            System.out.print(s + " ");

            for (int n : adj[s]) {
                if (!visited[n]) {
                    visited[n] = true;
                    queue.add(n);
                }
            }
        }
    }
}

Java

메인 함수 예제

Java

public class Main {
    public static void main(String[] args) {
        Graph g = new Graph(4);

        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);

        System.out.println("DFS starting from vertex 2:");
        g.DFS(2);

        System.out.println("\nBFS starting from vertex 2:");
        g.BFS(2);
    }
}

Java

✔️이 예제에서는 네 개의 정점을 가진 그래프를 생성하고, 정점 2에서 시작하는 DFS와 BFS 탐색을 수행합니다. DFS와 BFS는 탐색 순서가 다르기 때문에, 출력 결과도 다를 것입니다. DFS는 깊이를 우선으로 탐색하고, BFS는 너비를 우선으로 탐색합니다

마무리

이번 글을 통해 자바에서 자주 사용되는 스택, 큐, 그래프, DFS, BFS에 대한 기본적인 개념과 예제를 살펴보았습니다. 이러한 자료구조와 알고리즘은 애플리케이션 개발 및 알고리즘 문제 해결에 있어서 매우 중요한 역할을 합니다.

스택과 큐는 데이터를 관리하는 데 있어 기본적이면서도 효율적인 방법을 제공하며, 그래프와 이를 탐색하는 DFS, BFS 알고리즘은 데이터의 관계를 표현하고 이를 기반으로 복잡한 문제를 해결하는 데 유용합니다. 특히 알고리즘 문제를 풀 때 이들의 개념을 이해하는 것은 중요합니다.

앞으로도 다양한 문제에 도전하고, 그 과정을 기록하면서 더욱 성장하는 개발자가 되겠습니다.🚀

suover