[이코테]CHAPTER 05 DFS/BFS - 스택, 큐, 재귀함수, DFS

탐색(Search) :  많은 양의 데이터 중에서 원하는 데이터를 찾는 과정

대표적인 탐색 알고리즘으로 DFS, BFS , 이 두 알고리즘을 이해하기 위해서 스택, 큐, 재귀 함수를 알아야한다.

참고자료.

https://gmlwjd9405.github.io/2018/08/03/data-structure-stack.html

 

스택(Stack)= 박스 쌓기

: 한 쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO(Last In First Out) 또는 LILO(Last In Last Out) 구조

• 스택 메서드( java 라이브러리)

     * push(E item) : 해당 item을 Stack의 top에 삽입

     * pop( ): Stack의 top에 있는 item을 삭제하고 해당 Item을 반환

     * peek( ): Stack의 top에 있는 item을 삭제하지 않고 해당 item을 반환

     * empty( ): Stack이 비어 있으면 true, 비어 있지 않을 경우 false를 반환 

     * search (Object o) : 해당 Object의 위치를 반환, Stack의 top 위치는 1, 해당 Object가 없으면 -1을 반환

• Python의 리스트 관련 메서드 활용

     * append( ) : 해당 item을 Stack의 top에 삽입

     * pop( ): Stack의 top에 있는 item을 삭제하고 해당 Item을 반환

stack=[]

stack.append(5)#[5]
stack.append(2)#[5,2]
stack.append(3)#[5,2,3]
stack.append(7)#[5,2,3,7]
stack.pop()#[5,2,3]
stack.append(1)#[5,2,3,1]
stack.append(4)#[5,2,3,1,4]
stack.pop()#[5,2,3,1]
print(stack)#[5,2,3,1]
#최상단 원소부터 출력
print(stack[::-1])#[1,3,2,5]
print(len(stack))

- 배열과 달리 스택은 i번째 항목에 접근 불가

- 배열처럼 원소들을 하나씩 옆으로 밀어 줄 필요가 없다.

---

큐(Queue)

: 먼저 온 사람이 먼저 들어가기

from collections import deque

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

queue.append(5)#deque([5])
queue.append(2)#deque([5,2])
queue.append(3)#deque([5,2,3)
queue.append(7)#deque([5,2,3,7])
queue.popleft()#deque([2,3,7])
queue.append(1)#deque([2,3,7,1])
queue.append(4)#deque([2,3,7,1,4])
queue.popleft()#deque([3, 7, 1, 4])

print(queue)#deque([3, 7, 1, 4])
queue.reverse()#역순으로 바꾸기
print(queue)#deque([4, 1, 7, 3])

---

재귀 함수(Recursive Function)

: 자기 자신을 다시 호출하는 함수 

def recursive_function():
    print('재귀 함수를 호출')
    recursive_function()

recursive_function()

팩토리얼 함수 표현하기

def factorial_function(n):
    result=1
    for i in range(1,n+1):
        result*=i
    return result

#재귀 함수 팩토리얼
def factorial_recursive(n):
    if n<=1:
        return 1
    return n*factorial_recursive(n-1)

print(factorial_function(5))
print(factorial_recursive(5))

---

DFS (Depth -First Search ) : 깊이 우선 탐색,

그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 

1 -> 2 -> 7 -> 6 -> 8 -> 3 -> 4-> 5 순으로 

def dfs(graph,v,visted):
    #현재 노드를 방문 처리
    visted[v]=True
    print(v,end=' ')
    #현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visted[i]:#False값일 경우
            dfs(graph,i,visted)

graph=[
    [],#순서 0은 없으므로
    [2,3,8],#1이 연결된 노드 2,3,8
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]
#각 노드가 방문된 정보를 리스트를 자료형으로 표현(1차원 리스트)
visted=[False]*9#0부터 9이므로 9개

dfs(graph,1,visted)

자바 코드(https://github.com/ndb796/python-for-coding-test/blob/master/5/8.java)

package s14_dfs;

import java.util.ArrayList;

public class e01_5_8 {
    public static boolean[] visted=new boolean[9];
    public static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();

    public static void dfs(int x){
        //현재 방문한 노드 방문처리
        visted[x]=true;
        System.out.print(x+" ");
        for(int i=0;i<graph.get(x).size();i++){
            int y = graph.get(x).get(i);
            if(!visted[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);
    }
}