📕 꼭 필요한 자료구조 기초

탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정입니다. 그중에서 DFS와 BFS가 대표적인 탐색 알고리즘입니다. 이 두개의 알고리즘을 알려면 스택, 큐, 재귀 함수를 알아야 합니다.

📜 스택

LIFO 구조입니다.

import java.util.*;

public class Main {

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

        // 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
        s.push(5);
        s.push(2);
        s.push(3);
        s.push(7);
        s.pop();
        s.push(1);
        s.push(4);
        s.pop();
        // 스택의 최상단 원소부터 출력
        while (!s.empty()) {
            System.out.println(s.peek());
            s.pop();
        }
    }

}

📜 큐

FIFO 구조입니다.

import java.util.*;

public class Main {

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

        // 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
        q.offer(5);
        q.offer(2);
        q.offer(3);
        q.offer(7);
        q.poll();
        q.offer(1);
        q.offer(4);
        q.poll();
        // 먼저 들어온 원소부터 추출
        while (!q.isEmpty()) {
            System.out.println(q.poll());
        }
    }

}

📜 재귀함수

자기 자신을 다시 호출하는 함수입니다.

import java.util.*;

public class Main { // 무한히 나오는 재귀함수

    public static void recursiveFunction() {
        System.out.println("재귀 함수를 호출합니다.");
        recursiveFunction();
    }

    public static void main(String[] args) {
        recursiveFunction();
    }

}

🔔 재귀 함수의 종료 조건

재귀 함수를 문제 풀이에서 사용할 때는 반드시 종료조건을 명시해야합니다.

• 유클리드 호제법

import java.util.*;

public class Main {

    public static void recursiveFunction(int i) {
        // 100번째 호출을 했을 때 종료되도록 종료 조건 명시
        if (i == 100) return;
        System.out.println(i + "번째 재귀 함수에서 " + (i + 1) + "번째 재귀함수를 호출합니다.");
        recursiveFunction(i + 1);
        System.out.println(i + "번째 재귀 함수를 종료합니다.");
    }

    public static void main(String[] args) {
        recursiveFunction(1);
    }

}

🔔 재귀 함수와 스택

재귀 함수의 수행은 스택 자료구조를 이용합니다.

• 스택 자료구조 또는 반복문을 활용하는 문제를 재귀 함수로 간결하게 표현할 수 있습니다.
• DFS가 대표적입니다.

import java.util.*;

public class Main {

    // 반복적으로 구현한 n!
    public static int factorialIterative(int n) {
        int result = 1;
        // 1부터 n까지의 수를 차례대로 곱하기
        for (int i = 1; i <= n; i++) {
            result *= i;
        }
        return result;
    }

    // 재귀적으로 구현한 n!
    public static int factorialRecursive(int n) {
        // n이 1 이하인 경우 1을 반환
        if (n <= 1) return 1;
        // n! = n * (n - 1)!를 그대로 코드로 작성하기
        return n * factorialRecursive(n - 1);
    }

    public static void main(String[] args) {
        // 각각의 방식으로 구현한 n! 출력(n = 5)
        System.out.println("반복적으로 구현:" + factorialIterative(5));
        System.out.println("재귀적으로 구현:" + factorialRecursive(5));
    }

}

📕 탐색 알고리즘 DFS/BFS

📜 DFS

깊이 우선 탐색이라고 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘입니다.

🔔 그래프의 기본 구조

그래프는 Node와 Edge로 표현되며 이때 Node를 Vertex라고 말합니다.

• 2개의 Node가 Edge로 연결되어 있으면 '두 Node는 인접하다'라고 합니다.
• 따라서 '인접하다'를 표현할 때 2가지 방식으로 표현합니다.
  • 인접 행렬
  • 인접 리스트

📐 인접 행렬

2차원 배열로 그래프의 연결관계를 표현하는 방식

• 모든 관계를 저장하기 때문에 노드 개수가 많을 수록 메모리가 낭비됩니다.

import java.util.*;

public class Main {

    public static final int INF = 999999999; // 무한 비용 선언
    
    // 2차원 리스트를 이용해 인접 행렬 표현
    public static int[][] graph = {
        {0, 7, 5},
        {7, 0, INF},
        {5, INF, 0}
    };

    public static void main(String[] args) {
        // 그래프 출력
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                System.out.print(graph[i][j] + " ");
            }
            System.out.println();
        }
    }

}

📐 인접 리스트

리스트로 그래프의 연결관계를 표현하는 방식

• 연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용합니다.
• 하지만 이것 때문에 트걱정한 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 느립니다.
  • 연결된 데이터를 하나씩 확인해야 하기 때문입니다.

import java.util.*;

class Node {

    private int index;
    private int distance;

    public Node(int index, int distance) {
        this.index = index;
        this.distance = distance;
    }

    public void show() {
        System.out.print("(" + this.index + "," + this.distance + ") ");
    }
}

public class Main {

    // 행(Row)이 3개인 인접 리스트 표현
    public static ArrayList<ArrayList<Node>> graph = new ArrayList<ArrayList<Node>>();

    public static void main(String[] args) {
        // 그래프 초기화
        for (int i = 0; i < 3; i++) {
            graph.add(new ArrayList<Node>());
        }

        // 노드 0에 연결된 노드 정보 저장 (노드, 거리)
        graph.get(0).add(new Node(1, 7));
        graph.get(0).add(new Node(2, 5));

        // 노드 1에 연결된 노드 정보 저장 (노드, 거리)
        graph.get(1).add(new Node(0, 7));

        // 노드 2에 연결된 노드 정보 저장 (노드, 거리)
        graph.get(2).add(new Node(0, 5));

        // 그래프 출력
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < graph.get(i).size(); j++) {
                graph.get(i).get(j).show();
            }
            System.out.println();
        }
    }

}

🔔 DFS의 원리

DFS는 첫 시작 노드를 정해야하고 방문 기준을 정해야합니다. 보통의 방문기준은 번호가 낮은 인접 노드가 됩니다.

• 따라서 탐색 순서는 스택에 들어간 순서를 의미합니다.
• 실제로 스택을 사용하지 않아도 되며 탐색을 하는데 있어서 시간복잡도 O(n)을 가집니다.
• 스택 형태로도 되지만 재귀함수로 하면 더 간결하게 나옵니다.

📐 순서

1. 탐색 시작노드를 스택에 삽입하고 방문처리를 한다.
2. 스택의 최상단 노드에 방문하지 않은 인접노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

• 방문처리: 스택에 한 번 삽입되어 처리된 노드가 다시 삽입되지 않게 체크하는 것

import java.util.*;

public class Main {

    public static boolean[] visited = new boolean[9];
    public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();

    // DFS 함수 정의
    public static void dfs(int x) {
        // 현재 노드를 방문 처리
        visited[x] = true;
        System.out.print(x + " ");
        // 현재 노드와 연결된 다른 노드를 재귀적으로 방문
        for (int i = 0; i < graph.get(x).size(); i++) {
            int y = graph.get(x).get(i);
            if (!visited[y]) dfs(y);
        }
    }

    public static void main(String[] args) {
        // 그래프 초기화
        for (int i = 0; i < 9; i++) {
            graph.add(new ArrayList<Integer>());
        }

        // 노드 1에 연결된 노드 정보 저장 
        graph.get(1).add(2);
        graph.get(1).add(3);
        graph.get(1).add(8);
        
        // 노드 2에 연결된 노드 정보 저장 
        graph.get(2).add(1);
        graph.get(2).add(7);
        
        // 노드 3에 연결된 노드 정보 저장 
        graph.get(3).add(1);
        graph.get(3).add(4);
        graph.get(3).add(5);
        
        // 노드 4에 연결된 노드 정보 저장 
        graph.get(4).add(3);
        graph.get(4).add(5);
        
        // 노드 5에 연결된 노드 정보 저장 
        graph.get(5).add(3);
        graph.get(5).add(4);
        
        // 노드 6에 연결된 노드 정보 저장 
        graph.get(6).add(7);
        
        // 노드 7에 연결된 노드 정보 저장 
        graph.get(7).add(2);
        graph.get(7).add(6);
        graph.get(7).add(8);
        
        // 노드 8에 연결된 노드 정보 저장 
        graph.get(8).add(1);
        graph.get(8).add(7);

        dfs(1);
    }

}

📜 BFS

너비 우선 탐색이라는 의미입니다. 가까운 노드부터 탐색하는 알고리즘입니다. DFS는 가장 먼 노드부터 탐색하는 반면 BFS는 그 반대입니다.

• 간선이 모두 동일하고 최단경로를 구할 때 BFS를 이용해서 해결합니다.

🔔 BFS 원리

• 가까운 노드부터 탐색해 나가기 때문에, 큐 자료구조를 사용합니다.
• 큐에서 꺼낸 노드를 기준으로 인접하고 방문하지 않은 노드를 모두 큐에 넣습니다.

📐 순서

1. 탐색 시작노드를 큐에 삽입하고 방문처리를 한다.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 사입하고 방문처리를 한다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

import java.util.*;

public class Main {

    public static boolean[] visited = new boolean[9];
    public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();

    // BFS 함수 정의
    public static void bfs(int start) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(start);
        // 현재 노드를 방문 처리
        visited[start] = true;
        // 큐가 빌 때까지 반복
        while(!q.isEmpty()) {
            // 큐에서 하나의 원소를 뽑아 출력
            int x = q.poll();
            System.out.print(x + " ");
            // 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
            for(int i = 0; i < graph.get(x).size(); i++) {
                int y = graph.get(x).get(i);
                if(!visited[y]) {
                    q.offer(y);
                    visited[y] = true;
                }
            }
        }
    }

    public static void main(String[] args) {
        // 그래프 초기화
        for (int i = 0; i < 9; i++) {
            graph.add(new ArrayList<Integer>());
        }

        // 노드 1에 연결된 노드 정보 저장 
        graph.get(1).add(2);
        graph.get(1).add(3);
        graph.get(1).add(8);
        
        // 노드 2에 연결된 노드 정보 저장 
        graph.get(2).add(1);
        graph.get(2).add(7);
        
        // 노드 3에 연결된 노드 정보 저장 
        graph.get(3).add(1);
        graph.get(3).add(4);
        graph.get(3).add(5);
        
        // 노드 4에 연결된 노드 정보 저장 
        graph.get(4).add(3);
        graph.get(4).add(5);
        
        // 노드 5에 연결된 노드 정보 저장 
        graph.get(5).add(3);
        graph.get(5).add(4);
        
        // 노드 6에 연결된 노드 정보 저장 
        graph.get(6).add(7);
        
        // 노드 7에 연결된 노드 정보 저장 
        graph.get(7).add(2);
        graph.get(7).add(6);
        graph.get(7).add(8);
        
        // 노드 8에 연결된 노드 정보 저장 
        graph.get(8).add(1);
        graph.get(8).add(7);

        bfs(1);
    }

}

참조

https://velog.io/@sbinha/%EC%8A%A4%ED%83%9D-%ED%81%90
.
https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=kciter&logNo=100199946363
.
https://www.youtube.com/watch?v=RPSVXjcFbvA
.
https://velog.io/@cocoacolar/Algorithm-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B7%B8%EB%9E%98%ED%94%84Graph
.
https://velog.io/@jg31109/5.-%EC%9D%B4%EC%BD%94%ED%85%8C-BFSDFS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
.
https://mgyo.tistory.com/194
.
https://niklas-dev.tistory.com/19