[멋쟁이사자처럼 데이터분석 부트캠프 5기] 자료구조 양방향 연결리스트/ 트리/DFS/BFS

이번에는 자료구조이다.
대학에서 배운 경험이 있기 때문에 수월하게 들었다.

그 중에서도 헷갈리고 어려웠던 부분만 블로그로 복습하려고 한다.

0. Goal

양방향 연결리스트(DoubleLinkedList)
트리 표현하기
DFS
BFS
순으로 복습할 것이다.

DFS, BFS 알고리즘 확실하게 짚고 넘어가기 !!

---

 

1. 양방향 연결리스트

---

- 노드의 구성은 [이전노드 | 값  | 다음노드] 이다.
- 모든 노드는 head와 tail 사이에 위치한다.
- head, tail은 dummy 노드이다.

삽입 함수, 삭제함수, 리스트 출력 함수만 구현할 것이다.

class DoubleLinkedList :

    def __init__(self) :
        # 데이터를 담을 딕셔너리
        self.double_linked_list = {}
        # head 노드의 이름
        self.head_name = 'head'
        # tail 노드의 이름
        self.tail_name = 'tail'
        # head 노드 설정
        self.double_linked_list[self.head_name] = [None, None, self.tail_name]
        # tail 노드 설정
        self.double_linked_list[self.tail_name] = [self.head_name, None, None]
        # 노드 추가시 이름을 설정하기 위해 사용할 정수 변수
        self.node_index = 0


    def addData(self, value, head_or_tail = 1) :
        """
        데이터를 추가하는 메서드

        value
            저장할 값
        head_or_tail
            기본값은 1으로 설정한다.
            만약 0이 들어오면 제일 앞에 노드를 추가하고 1이 들어오면 제일 뒤에 추가한다.
        """
        # 새로운 노드를 만든다.
        new_node_name = f'node_{self.node_index}'
        self.node_index = self.node_index + 1
        self.double_linked_list[new_node_name] = [None, value, None]
        
        # head_or_tail 이 0이라면
        if head_or_tail == 0 :

            new_node = self.double_linked_list[new_node_name]
            head_node = self.double_linked_list[self.head_name]
            head_next_node_name = self.double_linked_list[self.head_name][2]
            head_next_node = self.double_linked_list[head_next_node_name] 
            # 새로운 노드의 이전 노드의 이름은 head로 설정하고
            new_node[0] = self.head_name
            # 새로운 노드의 다음 노드의 이름은 head 노드가 가지고 있는 다음 노드의 이름으로 설정한다.
            new_node[2] = head_next_node_name
            # head 의 다음노드의 이전 노드 이름을 새로운 노드의 이름으로 설정한다.
            head_next_node[0] = new_node_name
            # head 의 다음노드의 이름은 새로운 노드의 이름으로 설정한다.
            head_node[2] = new_node_name
            
        # head_or_tail이 1이라면
        elif head_or_tail == 1 :
            new_node = self.double_linked_list[new_node_name]
            tail_prev_node_name = self.double_linked_list[self.tail_name][0]
            tail_prev_node = self.double_linked_list[tail_prev_node_name]
            tail_node = self.double_linked_list[self.tail_name]
            # 새로운 노드의 이전 노드의 이름은 tail의 이전 노드 이름으로 설정한다
            new_node[0] = tail_node[0]
            # 새로운 노드의 다음 노드의 이름은 tail로 설정한다.
            new_node[2] = self.tail_name
            # tail 이전 노드의 다음 노드 이름을 새로운 노드의 이름으로 설정한다.
            tail_prev_node[2] = new_node_name
            # tail의 이전노드의 이름을 새로운 노드의 이름으로 설정한다.
            tail_node[0] = new_node_name

    def showAllData(self, head_or_tail = 0) :
        """
        데이터 전체를 출력해보는 메서드
        
        head_or_tail
            기본값은 0으로 설정한다.
            만약 0이 들어오면 제일 앞에서 부터 모든 데이터를 출력한다.
            만약 1이 들어오면 제일 뒤에서 부터 모든 데이터를 출력한다.
        """
        # head_or_tail이 0 이라면
        if head_or_tail == 0 :
            # 시작 노드를 head로 설정한다.
            current_node = self.double_linked_list[self.head_name]
            # 반복한다.
            while True :
                # 현재 노드를 다음 노드로 설정해준다.
                next_node_name = current_node[2]
                current_node = self.double_linked_list[next_node_name]
                # 현재 노드의 이름이 tail이 아니라면 출력한다
                if next_node_name != self.tail_name :
                    print(current_node[1])
                # 현재 노드의 이름이 tail이라면 중단한다.
                else :
                    break

        # head_or_tail이 1 이라면
        elif head_or_tail == 1 :
            # 시작 노드를 tail로 설정한다.
            current_node = self.double_linked_list[self.tail_name]
            # 반복한다.
            while True :
                # 현재 노드를 이전 노드로 설정해준다.
                prev_node_name = current_node[0]
                current_node = self.double_linked_list[prev_node_name]
                # 현재 노드의 이름이 head가 아니라면 출력한다.
                if prev_node_name != self.head_name :
                    print(current_node[1])
                # 현재 노드의 이름이 head라면 중단한다.
                else :
                    break

 
    
    def insertData(self, position, value, head_or_tail = 0) :
        """
        지정된 위치에 데이터를 삽입하는 메서드

        position
            데이터가 삽입될 위치

        value
            삽입될 데이터

        head_or_tail
            기본값은 0으로 설정한다.
            만약 0이 들어오면 head 부터 출발하여 position 번째에 value 값을 가진 노드를 삽입한다.
            만약 1이 들어오면 tail 부터 출발하여 position 번째에 value 값을 가는 노드를 삽입힌다.
        """
        
        # head_or_tail 이 0 이라면
        if head_or_tail == 0 :
            # 현재 노드를 head로 설정한다.
            current_node = self.double_linked_list[self.head_name]
            # 노드의 위치값을 0으로 설정한다.
            current_node_position = 0
            # 반복한다
            while True :
                # 현재 노드를 다음 노드로 설정한다.
                next_node_name = current_node[2]
                current_node = self.double_linked_list[next_node_name]
                # 현재 노드의 위치값과 찾고자 하는 위치가 같다면
                if current_node_position == position :
                    # 새로운 노드를 생성한다
                    new_node_name = f'node_{self.node_index}'
                    self.node_index = self.node_index + 1
                    new_node = [None, value, None]
                    self.double_linked_list[new_node_name] = new_node
                    # 새로운 노드의 이전 노드의 이름을 현재 노드의 이전 노드 이름으로 설정한다.
                    new_node[0] = current_node[0]
                    # 새로운 노드의 다음 노드의 이름을 현재 노드의 이름으로 설정한다.
                    new_node[2] = next_node_name
                    # 이전 노드의 다음 노드 이름을 새로운 노드의 이름으로 설정한다.
                    prev_node_name = current_node[0]
                    prev_node = self.double_linked_list[prev_node_name]
                    prev_node[2] = new_node_name
                    # 현재 노드의 이전 노드 이름을 새로운 노드의 이름으로 설정한다.
                    current_node[0] = new_node_name
                    # 중단한다.
                    break
                # 현재 노드의 위치값과 찾고자 하는 위치가 다르다면
                else :
                    # 만약 다음 노드가 tail 이라면 중단한다.
                    if current_node[2] == self.tail_name :
                        break
                    # 그렇지 않다면 노드의 위치값을 1 증가한다.
                    else :
                        current_node_position = current_node_position + 1

        # head_or_tail이 1 이라면
        elif head_or_tail == 1 :
            # 현재 노드를 tail로 설정한다.
            current_node = self.double_linked_list[self.tail_name]
            # 노드의 위치값을 0으로 설정한다.
            current_node_position = 0
            # 반복한다.
            while True :
                # 현재 노드를 이전 노드로 설정한다.
                prev_node_name = current_node[0]
                current_node = self.double_linked_list[prev_node_name]
                # 현재 노드의 위치값과 찾고자 하는 위치가 같다면
                if current_node_position == position :
                    # 새로운 노드를 생성한다
                    new_node_name = f'node_{self.node_index}'
                    self.node_index = self.node_index + 1
                    new_node = [None, value, None]
                    self.double_linked_list[new_node_name] = new_node
                    # 새로운 노드의 이전 노드의 이름을 현재 노드의 이전 노드 이름으로 설정한다.
                    new_node[0] = current_node[0]
                    # 새로운 노드의 다음 노드의 이름을 현재 노드의 이름으로 설정한다.
                    new_node[2] = prev_node_name
                    # 이전 노드의 다음 노드 이름을 새로운 노드의 이름으로 설정한다.
                    prev_node_name = current_node[0]
                    prev_node = self.double_linked_list[prev_node_name]
                    prev_node[2] = new_node_name
                    # 현재 노드의 이전 노드 이름을 새로운 노드의 이름으로 설정한다.
                    current_node[0] = new_node_name
                    # 중단한다.
                    break
                # 현재 노드의 위치값과 찾고자 하는 위치가 다르다면
                else :
                    # 만약 이전 노드가 head 라면 중단한다.
                    if current_node[0] == self.head_name :
                        break
                    # 그렇지 않다면 노드의 위치값을 1 증가한다.
                    else :
                        current_node_position = current_node_position + 1


  

    def removeData(self, position, head_or_tail) :
        """
        지정한 위치의 데이터를 삭제한다.

        position
            삭제할 데이터의 위치
            
        head_or_tail
            기본값은 0으로 설정한다.
            만약 0이 들어오면 head 부터 출발하여 position 번째의 노드를 제거한다.
            만약 1이 들어오면 tail 부터 출발하여 position 번째의 노드를 제거한다.
        """
        # head_or_tail 이 0 이라면
        if head_or_tail == 0 :
            # 현재 노드를 head로 설정한다.
            current_node = self.double_linked_list[self.head_name]
            # 노드의 위치값을 0으로 설정한다.
            current_node_position = 0
            # 반복한다
            while True :
                # 현재 노드를 다음 노드로 설정한다.
                next_node_name = current_node[2]
                current_node = self.double_linked_list[next_node_name]
                # 현재 노드의 위치값과 찾고자 하는 위치가 같다면
                if current_node_position == position :
                    # 이전 노드를 가져온다.
                    prev_node_name = current_node[0]
                    prev_node = self.double_linked_list[prev_node_name]
                    # 다음 노드를 가져온다.
                    next_next_node_name = current_node[2]
                    next_node = self.double_linked_list[next_next_node_name]

                    # 이전 노드의 다음 노드 이름을 다음 노드의 이름으로 설정한다.
                    prev_node[2] = next_next_node_name
                    # 다음 노드의 이전 노드 이름을 이전 노드의 이름으로 설정한다.
                    next_node[0] = prev_node_name
                    # 현재 노드를 제거한다.
                    del self.double_linked_list[next_node_name]
                    # 중단한다.
                    break
                # 현재 노드의 위치값과 찾고자 하는 위치가 다르다면
                else :
                    # 만약 다음 노드가 tail 이라면 중단한다.
                    if current_node[2] == self.tail_name :
                        break
                    # 그렇지 않다면 노드의 위치값을 1 증가한다.
                    else :
                        current_node_position = current_node_position + 1

        # head_or_tail이 1 이라면
        elif head_or_tail == 1 :
            # 현재 노드를 tail로 설정한다.
            current_node = self.double_linked_list[self.tail_name]
            # 노드의 위치값을 0으로 설정한다.
            current_node_position = 0
            # 반복한다.
            while True :
                # 현재 노드를 이전 노드로 설정한다.
                prev_node_name = current_node[0]
                current_node = self.double_linked_list[prev_node_name]
                # 현재 노드의 위치값과 찾고자 하는 위치가 같다면
                if current_node_position == position :
                    # 이전 노드를 가져온다.
                    prev_prev_node_name = current_node[0]
                    prev_node = self.double_linked_list[prev_prev_node_name]
                    # 다음 노드를 가져온다.
                    next_next_node_name = current_node[2]
                    next_node = self.double_linked_list[next_next_node_name]

                    # 이전 노드의 다음 노드 이름을 다음 노드의 이름으로 설정한다.
                    prev_node[2] = next_next_node_name
                    # 다음 노드의 이전 노드 이름을 이전 노드의 이름으로 설정한다.
                    next_node[0] = prev_prev_node_name
                    # 현재 노드를 제거한다.
                    del self.double_linked_list[prev_node_name]
                    # 중단한다.
                    break
                # 현재 노드의 위치값과 찾고자 하는 위치가 다르다면
                else :
                    # 만약 이전 노드가 head 라면 중단한다.
                    if current_node[0] == self.head_name :
                        break
                    # 그렇지 않다면 노드의 위치값을 1 증가한다.
                    else :
                        current_node_position = current_node_position + 1

 

✨ 기능 하나씩 구현하기

1. addData(value, head_or_tail)

값을 리스트의 앞 또는 뒤에 추가하는 메서드

• head_or_tail == 0: head 바로 뒤에 노드를 추가함 → 리스트의 맨 앞에 삽입됨
• head_or_tail == 1: tail 바로 앞에 노드를 추가함 → 리스트의 맨 뒤에 삽입됨

2. showAllData(head_or_tail)

리스트의 전체 데이터를 순서대로 출력하는 메서드

• head_or_tail == 0: 앞에서부터(head → tail)
• head_or_tail == 1: 뒤에서부터(tail → head)

3. insertData(position, value, head_or_tail)

특정 위치에 값을 삽입하는 메서드

• head부터 찾을지, tail부터 찾을지를 head_or_tail로 지정 가능
• 노드를 탐색하다가 원하는 위치에 도달하면, 그 사이에 새 노드를 삽입함

4. removeData(position, head_or_tail)

특정 위치의 데이터를 삭제하는 메서드

• 역시 양방향 탐색 가능
• 삭제 시에는 양쪽 노드의 연결 고리를 끊고 다시 이어주는 작업이 중요

 

 

2. 그래프

---

내가 작성할 트리 구조는 다음과 같다.

트리 구조를 코드로 작성하는 방법에는 딕셔너리 사용과 리스트 사용이 있다.

1. 이중 리스트로 트리 표현하기

tree1 = [
    'A',
    [
    'B',
        ['D', 'E']
    ],
     [
    'C',
         ['F', 'G']
     ],
]

리스트 안에 리스트 안에 리스트...
이렇게 작성하면 된다.

출력 또한 리스트 안에 리스트로 접근하면 된다.
D 를 찾고싶다면 전체 큰 리스트의 요소 중  [1]번째에 있고, 그 내부 리스트 중 [1]번 째 요소에 있고, 또 그 내부 리스트 중 [0]번째에 있다.
즉, tree1[1][1][0] 으로 접근하면 된다.

# 트리 출력해보기
print(tree1)
print(tree1[0])
print(tree1[1][0])
print(tree1[2][0])
print(tree1[1][1][0])
print(tree1[1][1][1])
print(tree1[2][1][0])
print(tree1[2][1][1])

['A', ['B', ['D', 'E']], ['C', ['F', 'G']]]
A
B
C
D
E
F
G

 

---

2. 딕셔너리로 트리 표현하기

tree2 = {
    'A' : ['B', 'C'],
    'B' : ['D', 'E'],
    'C' : ['F', 'G']
}

딕셔너리 가 훨씬 간결하게 표현된다. 👍

출력할 때는 리스트와 비슷하지만 다르다.
딕셔너리는 키 값을 가지고 있기 때문에 키값으로 접근한다.

D 를 찾고싶다면 키가 B인 리스트 안에 담겨 있으니 ['B'], 그 리스트의 [0]번째에 있다.
즉, tree2['B'][0] 으로 접근하면 된다.

print(tree2)
print(tree2['A'])
print(tree2['A'][0])
print(tree2['A'][1])
print(tree2[tree2['A'][0]][0])
print(tree2[tree2['A'][0]][1])

{'A': ['B', 'C'], 'B': ['D', 'E'], 'C': ['F', 'G']}
['B', 'C']
B
C
D
E

 

 

3. DFS

---

 

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

• 방식: 현재 정점에서 갈 수 있는 한 최대한 깊이(자식노드 방향으로) 들어가며 탐색
• 후퇴 조건: 더 이상 갈 수 있는 정점이 없으면 이전 단계로 "백트래킹"
• 구현 방식:
  • 재귀 함수 (스택 구조가 자연스럽게 따라옴)
  • 직접 스택 자료구조를 사용

 

구현할 그래프는 아래와 같다.

1) 트리 구조 작성하기

# 깊이 우선 순회
DFS그래프 = {
    'v1' : ['v2', 'v3'],
    'v2' : ['v1', 'v4', 'v5'],
    'v3' : ['v1', 'v6'],
    'v4' : ['v2'],
    'v5' : ['v2'],
    'v6' : ['v3']
}

 

2) depth_first_search 함수

# 깊이 우선 탐색을 하는 함수
def depth_first_search(DFS_graph, 방문노드, start) :
    """
        DFS_graph
            딕셔너리로 되어 있는 그래프 데이터
        방문노드
            방문한적이 있는 노드의 정보를 담을 리스트
        start
            시작 위치가 되는 노드의 이름
    """
    # 시작 노드는 무조건 방문한 것으로 취급한다.
    방문노드.append(start)

    # 현재 노드의 하위 노드를 가져와 그 수 만큼 반복한다
    for node in DFS_graph[start]:
        # 만약 현재 방문한 노드가 이미 방문한 노드라면
        if node in 방문노드 :
            print(f'현재 방문한 노드 : {node}')
            print(f'지금까지 방문한 모든 노드 : {방문노드}')
            print()
        # 만약 현재 방문한 노드가 이미 방문한 노드가 아니라면
        elif node not in 방문노드:
            print(f'현재 방문한 적이 없는 노드 : {node}')
            # 다음 방문 처리를 위해 함수를 다시 호출한다.
            depth_first_search(DFS_graph, 방문노드, node)

참고)
수업 땐 탐색 과정을 출력할것인지에 대한 변수인 verbose를 사용했지만,
우선 DFS 알고리즘에만 집중하기 위해 verbose는 빼고 정리를 했다.

3) 출력

# 결과를 담을 리스트
result1= []
depth_first_search(DFS그래프, result1, 'v1')
result1

현재 방문한 적이 없는 노드 : v2
현재 방문한 노드 : v1
지금까지 방문한 모든 노드 : ['v1', 'v2']

현재 방문한 적이 없는 노드 : v4
현재 방문한 노드 : v2
지금까지 방문한 모든 노드 : ['v1', 'v2', 'v4']

현재 방문한 적이 없는 노드 : v5
현재 방문한 노드 : v2
지금까지 방문한 모든 노드 : ['v1', 'v2', 'v4', 'v5']

현재 방문한 적이 없는 노드 : v3
현재 방문한 노드 : v1
지금까지 방문한 모든 노드 : ['v1', 'v2', 'v4', 'v5', 'v3']

현재 방문한 적이 없는 노드 : v6
현재 방문한 노드 : v3
지금까지 방문한 모든 노드 : ['v1', 'v2', 'v4', 'v5', 'v3', 'v6']

['v1', 'v2', 'v4', 'v5', 'v3', 'v6']

 

 

 

4. BFS

---

 

BFS(Breadth-First-Search), 너비우선탐색

• 방식: 현재 정점에서 인접한 정점을 "넓게" 먼저 탐색
• 진행 순서: 시작 노드에서 가까운 노드부터 차례대로 방문
• 자료구조: 큐(Queue)를 사용하여 방문할 정점을 순서대로 관리

 

1) 트리 구조 작성하기

BFS그래프 = {
    'v1' : ['v2', 'v3'],
    'v2' : ['v1', 'v4', 'v5'],
    'v3' : ['v1', 'v6'],
    'v4' : ['v2'],
    'v5' : ['v2'],
    'v6' : ['v3']
}

 

2) breadth_first_search 함수 

여기서 deque(덱)이라는 자료구조를 사용한다.
deque은 큐 처럼 사용할 수 있는 양방향 자료구조이다.

from collections import deque

# 너비 우선 탐색을 위한 함수
def breadth_first_search(BFS_graph, result_list, start):
    # 시작 위치의 값을 Deque에 저장한다.
    q1 = deque([start])

    # 큐에 데이터가 아무것도 없을 때 까지 반복한다.
    while q1 :
        # 큐에 들어있는 노드를 추출한다.
        node = q1.pop()
        # 방문한 적이 있다면 다음 반복으로 넘어간다.
        if node in result_list :
            continue

        # 만약 현재 지점이 방문한 적이 없다면 리스트에 추가한다.
        else:
            print(f'현재 방문한 노드 : {node}')
            result_list.append(node)
            print(f'방문노드의 모든 경로 출력 : {result_list}')
            print()

            # 현재 방문한 하위 노드들은 모두 que에 추가한다.
            q1.extendleft(BFS_graph[node])

 

일반적인 BFS에서는 popleft()로 왼쪽에서 꺼내고, append()로 오른쪽에 추가하는 방식이 일반적이다.
하지만 이 코드는 반대로 왼쪽에 추가 (extendleft) + 오른쪽에서 꺼냄 (pop) = 동일한 결과!

결국 선입선출 식으로 출력이 되는것이다.

 

3) 출력

result1 = []
breadth_first_search(BFS그래프, result1,'v1')
result1

현재 방문한 노드 : v1
방문노드의 모든 경로 출력 : ['v1']

현재 방문한 노드 : v2
방문노드의 모든 경로 출력 : ['v1', 'v2']

현재 방문한 노드 : v3
방문노드의 모든 경로 출력 : ['v1', 'v2', 'v3']

현재 방문한 노드 : v4
방문노드의 모든 경로 출력 : ['v1', 'v2', 'v3', 'v4']

현재 방문한 노드 : v5
방문노드의 모든 경로 출력 : ['v1', 'v2', 'v3', 'v4', 'v5']

현재 방문한 노드 : v6
방문노드의 모든 경로 출력 : ['v1', 'v2', 'v3', 'v4', 'v5', 'v6']

['v1', 'v2', 'v3', 'v4', 'v5', 'v6']

 

 

 

---

느낀점 💭

솔직히 개념 자체는 어렵지 않다. 근데 구현하는게 진짜 머리 터진다.
코드는 가독성이 좋아야하는데 위 코드는 변수명이 길다보니 한 줄 한 줄 읽기가 조금 버겁다.
그리고 클래스 생성자는 아직까지도 생소하다...언제쯤 익숙해질지 ㅎ
특히 이번 문제 조건이 순방향/역방향 모두 구현하는거라 코드가 너무 복잡해진 것 같다.

트리 구조를 작성하는 방법은 다 까먹었었는데, 다시 배울 수 있어서 좋았다.
DFS, BFS 는 하위 노드로 어떻게 접근 할지 가 가장 중요한 부분인거 같다 !!

 

다음은 여전히 머리에 섞여있는 정렬 글로 돌아오겠다...💣

 

출처 : 멋쟁이사자처럼