알고리즘 문제를 풀다 보면 정말 많은 탐색 알고리즘을 요구하는 문제들을 만납니다. 먼저 탐색(Search)이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말하며, 문제에서는 주로 그래프, 트리 등의 자료구조 안에서 탐색하는 문제들이 자주 출제됩니다.

Graph

탐색 알고리즘에 들어가기에 앞서 먼저 그래프에 대해서 알아봅니다.

• 그래프는 node(노드)와 edge(간선)으로 표현되며, 이떄 노드를 vertex(정점)이라고도 합니다.
• 그래프 탐색이란, 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말합니다.
• 두 노드가 간선으로 연결되어 있다면 '두 노드는 인접하다'라고 합니다.

그래프 표현 방법

그래프를 표현하는 방법에는 두가지 방법이 있습니다.

• 인접 행렬 : 2차원 배열로 그래프의 연결 관계를 표현.
• 인접 리스트 : 리스트로 그래프의 연결 관계를 표현.

인접 행렬 방식 예제

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();
        }
    }
}

인접 리스트 방식 예제

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(Depth-First-Search): 깊이 우선 탐색 알고리즘
• 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
• 스택 자료구에 기초하는 알고리즘
• 모든 노드를 방문하고자 하는 경우

동작 방식

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

스택

스택(Stack)은 선입후출 구조 또는 후입선출 구조의 자료구조(Data Structure)이며, 주로 구조를 박스 쌓기에 비유할 수 있습니다.

import java.util.Stack;

Stack<Integer> stack = new Stack<>();
stack.push(1);     // 스택에 값 추가
stack.peek();      // 스택의 가장 상단의 값 출력
stack.pop();       // 스택의 가장 상단의 값 제거
stack.clear();     // 스택 초기화
stack.size();      // 스택의 크기 출력
stack.empty();     // 스택이 비어있는지 확인 (boolean)
stack.contains(1); // 스택에 1의 값이 있는지 확인 (boolean)

DFS 예제

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>());
        }

        // 노드에 연결된 노드 정보 저장
        graph.get(1).add(2);
        // ... 중략 ...
        graph.get(8).add(7);

        dfs(1);
    }
}

---

BFS

• BFS(Breadth First Search) : '너비 우선 탐색' 알고리즘
• 가까운 노드부터 탐색하는 알고리즘
• 선입선출 방식의 큐 자료구조를 이용하는것이 정석.
• 주로 두 노드 사이의 최단 경로를 찾고 싶을 때 사용.

동작 방식

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

큐

큐(Queue)는 흔히 큐를 대기 줄에 비유할 수 있습니다. 먼저 온 사람이 먼저 나가는 선입선출 자료구조입니다.

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

Queue<Integer> queue = new LinkedList<>(); // Integer 형 큐 선언
queue.add(1);    // 큐에 값 추가
queue.offer(3);  // 큐에 값 추가
queue.peek();    // 큐의 첫번째 값 출력
queue.poll();    // 큐의 첫번째 값을 반환하고 제거 비어있다면 null
queue.remove();  // 큐의 첫번째 값 제거
queue.clear();   // 큐 초기화

예제

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>());
        }

        // 노드에 연결된 노드 정보 저장
        graph.get(1).add(2);
        // ... 중략 ...
        graph.get(8).add(7);

        bfs(1);
    }
}

출처

• 나동빈 저자님의 <이것이 취업을 위한 코딩 테스트다 with 파이썬> - Github 바로가기