[python] Stack과 DFS

---

자료 구조인 Stack과 DFS(깊이 우선 탐색)에 대해 알아보도록 하자.

 

1. Stack (스택)

스택(stack)은 제한적으로 접근할 수 있는 나열 구조로, 접근 방법은 항상 목록의 끝에서만 일어난다.

따라서 후입선출 (Last In First Out—LIFO)의 특성을 가지는 자료구조라고 불리운다.

 

이와 반대인 선입선출의 구조를 가진 queue도 존재하지만, 이번 글에서는 스택만 다루도록 한다.

 

 

 

후입선출의 구조를 가진 자료구조인 스택 (stack)

 

스택에서는 다음과 같은 중요한 연산이 존재한다.

 

S.size()	현재 스택에 들어있는 데이터 원소 개수를 반환한다.
S.pop()	스택의 가장 윗 데이터를 반환하고, 삭제한다.
S.push()	스택의 가장 윗 데이터를 추가한다.
S.empty()	스택이 비었다면 1, 그렇지 않다면 0을 반환한다.
S.full()	스택이 차있다면 1, 그렇지 않다면 0을 반환한다.
S.peek()	스택의 가장 윗 데이터를 반환한다.

 

 

 

클래스를 이용한 스택의 구현 ( python )

 

class stack:
    def __init__(self, size):
        self.size = size
        self.top = -1
        self.items = [None] * self.size
 
    def is_empty(self):
        return True if self.top == -1 else False
 
    def is_full(self):
        return True if self.top == self.size else False
 
    def push(self, item):
        self.item = item
        if self.top < self.size:
            self.top += 1
            self.items[self.top] = self.item
        else:
            raise Exception("stack is full")
 
    def pop(self):
        if self.is_empty():
            raise Exception("It is empty")
        else:
            value = self.items[self.top]
            self.items[self.top] = None
            self.top -= 1
            return value
 
    def peek(self):
        if self.is_empty():
            raise Exception("It is empty")
        else:
            return self.items[self.top]
 
    def __str__(self):
        self.stack = ""
        for item in self.items:
            self.stack += item
            return self.stack

 

---

2. DFS (Depth - First - Search)

DFS (깊이 우선 탐색)이란?

시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더 이상 갈 곳이 없게 되면,

가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와서 다른 방향의 정점으로 탐색을 계속 반복하여, 

결국 모든 정점을 방문하는 순회 방법이다.

=> 가장 마지막에 만났던 갈림길의 정점으로 되돌아가 다시 깊이 우선 탐색을 반복해야 하므로 후입선출 구조의 stack을 사용한다.

 

 

깊이 우선 탐색 (DFS)

 

 

•  장점
  • 단지 현 경로상의 노드(정점)만을 기억하면 되므로, 저장 공간의 수요가 비교적 적다.
  • 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.

 

• 단점
  • 해가 없는 경로에 깊이 빠질 가능성이 크다.
  • 얻어진 해가 최단 경로가 된다는 보장이 없다.

 

DFS 알고리즘

1) 시작 정점 v를 결정하여 방문한다.

 

2) 정점 v에 인접한 정점 중에서.

    1. 장문하지 않은 정점 w가 있으면, 정점 v를 스택에 push 하고 정점 w를 방문한다. 그리고 w를 v로 하여 다시 2)를 반복한다.

    2. 방문하지 않은 정점이 없으면, 탐색의 방향을 바꾸기 위해서 스택을 pop하여 받은 가장 마지막 방문 정점을 v로 하여 

         다시 2)를 반복한다.

 

3) 스택이 공백이 될 때까지 2)를 반복한다.

 

 

 

 

 

DFS의 구현 방법 - 인접 행렬

위 그림을 기준으로 아래와 같이 행렬을 이용하여 정점들 간의 관계를 표현한다.

 

 

인접 행렬

 

 

 

DFS의 구현 방법 - 인접 리스트

list방식으로 각 정점이 연결된 노드의 정보를 저장하는 방식이다.

 

 

인접 리스트

 

 

 

인접행렬을 이용한 DFS 구현.

입력 값.
7 8
1 2 1 3 2 4 2 5 4 6 5 6 6 7 3 7

 

def dfs(n): # n은 시작 정점
    global visited # 함수 내에서 사용하기 위해 visited는 전역변수로 선언
    stack = [n]
    while stack: # 스택이 비어버리면 종료
        n = stack.pop()
        if visited[n] == 0: # 방문하지 않은 정점이라면,
            visited[n] = 1 # 방문 처리를 하고,
            print(f"방문정점 : {n}, 방문 체크 : {visited}")
            for j in range(1, V + 1):
                if g[n][j] == 1 and visited[j] == 0: # 연결되어있고, 방문하지 않았다면
                    stack.append(j) # 스택에 해당 노드를 넣어준다.
 
 
V, E =  map(int, input().split()) # V : 정점의 개수 // E : 간선의 개수
temp = list(map(int, input().split())) # 연결된 간선을 리스트화
# 스택, visited
 
g = [[0] * (V + 1) for _ in range(V + 1)] # 인접 행렬 리스트 제작
 
for i in range(0, E):
    g[temp[i * 2]][temp[(i * 2) + 1]] = 1 # 간선이 양방향일 경우.
    g[temp[(i * 2) + 1]][temp[i * 2]] = 1 # temp를 기준으로 인접행렬 리스트를 제작한다.
 
# 한번 갔던 길을 다시 가지 않기 위해 visited라는 방문유무를 체크하는 리스트를 사용한다.
visited = [0] * (V + 1)
dfs(1) # 시작노드 : 1번

 

 

---

다음 포스팅에서는 DFS와 같이 언급되는 BFS (너비 우선 탐색)에 대해서 포스팅 해야겠다.