[코딩 테스트 준비] 그래프

강의명: 패스트캠퍼스: 개발자 취업 합격 패스 With 코딩테스트, 기술면접 초격차 패키지 Online

내용: Part 2. 알고리즘 이론 _ Ch 17-18 그래프 기본 구조 및 탐색 알고리즘

 

Ch 17. 그래프 이해와 자료구조

(무)방향(Un/Directed) 그래프(Graph): 정점(Vertex) or 노드(Node) + 간선(Edge)

방향 A to B <A, B> <B, A>

무방향 (A, B)

가중치 (Weighted) 그래프 or 네트워크(Network)

연결 그래프

비연결 그래프

중복 방문 노드가 없는 단순 경로(Simple Path) 중 처음과 끝 노드가 같은 경로: 사이클(Cycle)

사이클이 없는 그래프: 비순환 그래프

완전 그래프

 

Ch 18. 그래프 기본 탐색 알고리즘

 

필요 자료구조

1. 방문한 노드: O(1)로 방문 여부를 확인할 수 있도록 HashMap으로 구현
- Python에서는 not in 키워드로 가능

 

BFS 너비 우선 탐색: O(V + E)

2. 방문할 노드: 큐 (FIFO)

 

DFS 깊이 우선 탐색: O(V + E)

2. 방문할 노드: 스택 (LIFO)

 

개인 실습. 키보드 자판으로 만든 그래프 탐색

결과

BFS

DFS

과정 및 코드 

1. 그래프 생성

import pprint

pp = pprint.PrettyPrinter().pprint


graph = dict()

# 그래프 입력 정보
list_in = [
    ["1", "2", "3", "4", "5", "6", "7", "8", "9", "0"],
    ["Q", "W", "E", "R", "T", "Y", "U", "I", "O", "P"],
    ["A", "S", "D", "F", "G", "H", "J", "K", "L", ";"],
    ["Z", "X", "C", "V", "B", "N", "M", ",", ".", "/"],
]

# 그래프 생성 과정
nRows = len(list_in)
for row in range(0, nRows):
    nCols = len(list_in[row])
    for col in range(0, nCols):
        value_list = []
        for modi in [[-1, 0], [+1, 0], [0, -1], [0, +1]]:
            r = row + modi[0]
            c = col + modi[1]

            if r == -1:
                r = nRows - 1
            elif r == nRows:
                r = 0
            else:
                c %= nCols

            try:
                value_list.append(list_in[r][c])
            except:
                # null pointer exception
                pp([r, c])

        graph[list_in[row][col]] = value_list

print("그래프 연결 정보")
pp(graph)

 

2. 그래프 탐색

2-1. BFS

def BFS(start_node):
    visited_node = {}
    node_next = []

    node_next.append(start_node)

    while node_next:
        cur = node_next.pop(0)
        if cur not in visited_node.keys():
            visited_node[cur] = True
            node_next.extend(graph[cur])

    return visited_node


print("BFS 탐색 결과")
pp(BFS("G").keys())

2-2. DFS

def DFS(start_node):
    visited_node = {}
    node_next = []

    node_next.append(start_node)

    while node_next:
        cur = node_next.pop()
        if cur not in visited_node.keys():
            visited_node[cur] = True
            node_next.extend(graph[cur])

    return visited_node


print("DFS 탐색 결과")
pp(DFS("G").keys())

 

 

BFS에 대한 시각화 코드

import os
import numpy as np
import matplotlib.pyplot as plt
import imageio


def BFS_visualize(start_node):
    visited_node = {}
    node_next = []

    node_next.append(start_node)

    while node_next:
        cur = node_next.pop(0)
        if cur not in visited_node.keys():
            visited_node[cur] = True
            print_current_state(visited_node.keys())
            node_next.extend(graph[cur])

    return visited_node


# graph 각 값에 대한 위치 정보 생성
list_in_info = {}
nRows = len(list_in)
for row in range(0, nRows):
    nCols = len(list_in[row])
    for col in range(0, nCols):
        list_in_info[list_in[row][col]] = (row, col)

data = []
key_in = []
cur = [[0 for col in range(10)] for row in range(4)]


def print_current_state(key_list):
    for k in key_list:
        if k not in key_in:
            key_in.append(k)
            cur[list_in_info[k][0]][list_in_info[k][1]] = 1
            data.append(np.array(cur))


BFS_visualize("G")

fig, ax = plt.subplots()

filenames = []

for i, img in enumerate(data):
    ax.clear()
    ax.imshow(img)
    ax.set_title(f"frame {i}")
    filename = f"{i}.png"
    filenames.append(filename)
    plt.savefig(filename)
    plt.pause(0.1)

# build gif

gif_config = {
    "loop": 0,  ## 0으로 세팅하면 무한 반복, 3으로 설정하면 3번 반복
    "duration": 0.5,  ## 다음 화면으로 넘어가는 시간
}

images = []
for filename in filenames:
    image = imageio.imread(filename)
    images.append(image)
imageio.mimsave(
    "BFS_visualized.gif",
    images,  ## 이미지 리스트
    format="gif",  ## 저장 포맷
    **gif_config,  ## 부가 요소
)

# Remove files
for filename in set(filenames):
    os.remove(filename)

 

DFS는 BFS_visualize 함수에서 다음 내용을 수정하면 된다.

cur = node_next.pop(0) >>  cur = node_next.pop()