크래프톤 정글 2기 3주차 후기

3주차를 마무리했다.

 

이번 주에서 다뤘던 주제는 그래프 탐색과 BFS, DFS이다.

코딩 테스트에서 자주 출제되는 유형이기 때문에 이전 주제들보다 더 신경을 많이 썼다고 생각했지만

3 주차 시험 3문제 중 1개밖에 못 풀었다. 이유는 단순히 내 학습량이 부족해서인 것 같다.

추가적으로 부족한 점을 채우기위해 따로 문제를 찾아서 풀어본 적이 없는데

NHN 아카데미 때 매일 주어지는 과제를 따라가기 급급해 내 개인학습 시간이 없었을 때와는 상황이 다름에도

똑같은 태도로 정글에 임하고 있는 거 아닌가 라는 생각이 들었다.

뒤에서 따라가는 수준에서 만족하자고 들어온 곳이 아니기때문에 마음을 다잡고 더 열심히 해야겠다. 

 

 

이번주 키워드

DFS(Depth First Search) - 말 그대로 깊이 우선 탐색 그래프의 깊은 부분을 우선적으로 탐색하는 알고리즘

스택 자료구조를 사용하거나 재귀로 구현한다. 시간복잡도는 O(N)이다. (한놈만 패면서 내려가)

DFS 동작과정(스택)

1. 탐색노드를 스택에 삽입하고 방문처리

2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있다면 그 노드를 스택에 넣고

방문 하지않은 노드가 없으면 스택의 최상단 노드를 꺼낸다.(방문 안한 노드 찾는거)

3. 2번의 과정을 수행하지 못할때까지 반복한다.

def DFS(graph, start_node):
    # 1개의 dict와 2개의 list
    need_visit, visited = list(), list()
    # 초기화
    need_visit.append(start_node)
    # while pop에서는 need_visit리스트의 원소들을 삭제하는 구조를 취한다. 
    #스택을 활용해서 쉽게 DFS를 구현할 수 있지만 
    #이 방식은 순회의 방향이 오른쪽 노드를 우선으로 탐색하게 된다.
    while need_visit:
        node = need_visit.pop()
        #그래프의 그림을 보며 따라가보면 쉽게 이해할 수 있다.
        if node not in visited:
            visited.append(node)
            need_visited.extend(graph[node])     
    return visited

 

 

DFS 재귀

graph = [
    [],      # 0
    [2, 3],  # 1 
    [4, 5],  # 2
    [6],     # 3
    [2, 5],  # 4
    [2, 4],  # 5
    [3, 7],  # 6
    [6]      # 7
]

# 방문 정보를 기록하기 위한 리스트
visited = [False] * 8

def dfs(v):
    # 방문 표시
    visited[v] = True
    print(v, end=' ')
    # 그래프를 순환하면서 인접 노드들을 방문
    for i in graph[v]:
        # 만약 방문하지 않은 노드가 있다면
        if not visited[i]:
            # 탐색 시작
            dfs(i)

# 탐색 시작 노드 1을 넣어주며 dfs() 실행
dfs(1)

 

BFS(Breadth First Search) - 이름 그대로 너비를 우선적으로 탐색하는 알고리즘

DFS 처럼 한놈만 패고 내려가는게 아니라 시작점인 루트와 같은 거리에 있는 노드들을 다 패면서 방문한다.

가까운 노드부터 우선순위를 가져야 하기때문에 구현시 자료구조 큐를 활용해서 구현

BFS 동작과정(큐)

1. 큐 생성 및 큐에 시작 노드 삽입, 방문 처리

2. 큐에서 노드를 꺼내 해당 노드의 인접노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리

3. 2번 과정을 수행할 수 없을때까지 반복

 

BFS 큐

from collections import deque

graph = [
    [],      # 0
    [2, 3],  # 1 
    [4, 5],  # 2
    [6],     # 3
    [2, 5],  # 4
    [2, 4],  # 5
    [3, 7],  # 6
    [6]      # 7
]

visited = [False] * 8

def bfs(v):
    # 큐 생성 및 큐에 시작 노드 삽입
    q = deque()
    q.append(v)
    # 아직 방문해야 하는 노드가 있다면
    while q:
        # 큐에서 노드를 꺼내서 x에 저장
        x = q.popleft()
        print(x, end=' ')
        # 그래프를 탐색하다가 방문하지 않은 노드가 있다면
        for i in graph[x]:
            if not visited[i]:
                # 큐에 방문하라고 삽입하고 방문 처리
                q.append(i)
                visited[i] = True

bfs(1)