그래프 탐색 알고리즘(DFS/BFS)(1) - 스택과 큐

그래프 탐색 알고리즘(DFS/BFS)

• 탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
• 대표적인 그래프 탐색 알고리즘으로는느 DFS와 BFS가 있다.
• DFS/BFS는 코딩 테스트에서 매우 자주 등장하는 유형이므로 반드시 숙지해야 한다.

 

DFS와 BFS에 대해 알아보기 전에 반드시 알고 가야 할 자료구조 두 가지가 있다.

 

 

스택 자료구조

• 먼저 들어 온 데이터가 나중에 나가는 형식(후입 선출, LIFO)의 자료구조이다.
• 입구와 출구가 동일한 형태로 스택을 시각화할 수 있다.

 

스택 동작 예시

삭제 시 마지막에 들어왔던 7이 나간다.

 

 

스택 구현 예제

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

}

# 파이썬

stack = []

# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(1)
stack.append(4)
stack.pop()

print(stack) # 최하단 원소부터 출력
print(stack[::-1]) # 최상단 원소부터 출력

 

 

 

큐 자료구조

• 먼저 들어 온 데이터가 먼저 나가는 형식(선입선출, 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());
        }
    }

}

# 파이썬

from collections import deque 

# 큐(Queue) 구현을 위해 deque 라이브러리 사용
queue = deque()

# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft()
queue.append(1)
queue.append(4)
queue.popleft()

print(queue) # 먼저 들어온 순서대로 출력
queue.reverse() # 다음 출력을 위해 역순으로 바꾸기
print(queue) # 나중에 들어온 원소부터 출력