DFS, BFS

탐색이란 원하는 데이터를 찾는 과정이다. 코딩테스트에서 자주 나오는 단골문제이니 꼭 알아두도록 하자.

알아두면 좋은 개념: 재귀함수, 스택, 큐

 

DFS

깊이 우선 탐색으로 깊은 부분을 우선적으로 탐색하는 알고리즘

스탁, 재귀 함수 이용한다.

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

2. 스택의 최상단 노드에 망문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.

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

def dfs(graph, v, visited):
    visited[v] = True
    print(v,end=' ')
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

BFS

너비 우선 탐색 , 가까운 노드부터 우선 탐색

Queue 사용. 특정 조건에서 최단 경로 알고리즘이다.

큐에서 꺼내면서 해당하는 수 주변에 있는 방문처리 확인. 간선의 길이가 동일할때 자주 사용됨.

ex) 연결 노선 찾기

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.

2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 큐에 삽입하고 방문처리한다.

3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.

def bfs(graph, start, visited):
    queue = deque([start])
    visited[start] = True
    while queue:
        v = queue.popleft()
        print(v,end=' ')
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

파이썬에서는 deque를 사용하면 bfs를 더 쉽게 구현 가능하다.