코딩테스트 :: 스텍(2)

스택 / 큐 => 탐색 (그래프및 트리와 연결)

 

용어	설명
탐색	많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다. 코테 문제에서는 그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제가 아주 많이 등장한다. (DFS / BFS) * (DFS / BFS)은 스택과 큐를 제대로 이해하여야 합니다.
자료구조	데이터를 효율적으로 저장하고 관리하기 위한 체계(구조) * 스택/큐 => 자료구조의 기초 개념 위의 두 핵심적인 함수에는 삽입(push)/삭제(pop)가 존재함! 그 이외에도 오버 플로와 언더플로가 있다.
오버 플로	특정한 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입연산을 수행할 때 발생하는 것 (=저장공간을 벗어난 상태)
언더 플로	특정한 자료구조에 데이터가 전혀 들어있지 않은 상태에서 삭제 연산을 수행하는 것을 의미한다. (=비어있는 곳에서 자꾸 삭제하려고할때)
재귀함수	재귀함수는 자기 자신을 다시 호출하는 함수를 의미함 (DFS / BFS)를 구현하려면 재귀함수를 이해해야한다.

 

---

DFS(깊이 우선 탐색)알고리즘 

=>  깊은곳부터 우선적으로 탐색하는 알고리즘을 이야기함

노드 = 버택 (Vertex)

프로그래밍(코테)에서는 크게 2가지 방식으로 표현한다.

1. 인접행렬 => 2차원 배열로 연결된 관계를 표현

2. 인접리스트 => 리스트로 연결된 관계를 표현 (링크드 리스트(Linked List) 방식에 의한 연결)

---

DFS는 깊이 우선 탐색 알고리즘은 '스택'자료구조를 이용하여 동작한다.


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

위의 방식들은 stack임을 알아두자!

즉 순서대로 하자면

위의 순서대로  in-out 이 됩니다.

---

graph : 전체 그래프

v : (vertex) 노드

visited :방문했던거 체크

##재귀함수

def dfs(graph, v,visited):
    #현재 방문한 노드를 처리하는 코드
    visited[v] = True
    print(v, end=' ')
    #현재 노드와 연결된 다음 노드를 재귀적으로 호출하여 방문
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i , visited)

#각 노드가 연결되어 있는 정보 리스트를 구현
graph = [
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

# 각 노드가 방문된 정보를 리스트 자료형으로 표현하는 코드
visited = [False] * 9

# 정의 DFS 함수를 호출
dfs(graph, 1, visited)