[이것이 코딩테스트다 Ch5 ] DFS와 BFS

---

1. 스택과 큐

(1) 스택
- 후입선출
- 삽입은 append(n) , 삭제는 pop()

(2) 큐
- 선입선출
- 파이썬에선 큐 구현을 위해 deque 라이브러리를 사용한다.
- 삽입 append(n), 삭제 popleft()
- queue 라이브러리 대신 deque 라이브러리를 사용하는 이유? (from collections import deque)
>> deque는 스택과 큐의 장점을 모두 채택한 것이라서 데이터를 넣고 빼는 속도가 훨씬 빠르기 때문!
>> 코테에서는 collections 모듈과 같은 기본 라이브러리 사용을 허용함

 

: 코테 라이브러리에 대한 내용이 자세히 잘 나와있어서 주소 첨부!
https://velog.io/@koyo/python-docs-6

[내가 보려고 적는 파이썬] 주요 라이브러리

---

2. 재귀함수

- 재귀함수의 수행은 스택 자료구조를 이용한다.
>> 함수 호출 시 가장 마지막에 호출한 함수의 수행이 끝나야 그 앞의 함수 호출이 가능해진다.

---

 

[1] DFS (Depth-First Search)

- 깊이 우선 탐색
- 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
- 스택 자료구조를 이용
- 최대한 멀리 있는 노드를 우선으로 탐색 (<-> BFS)

---

인접 행렬

: 2차원 배열로 그래프의 연결 관계를 표현하는 방식
>> 인접 행렬은 2차원 리스트로 구현

>> 모든 행렬의 정보를 다 넣는다.

인접 리스트

: 리스트로 그래프의 연결 관계를 표현하는 방식
>> 인접 리스트는 연결 리스트를 이용, 파이썬에서는 단순히 2차원 리스트를 이용하면 된다.

>> 연결 정보만을 저장한다.

* 메모리 측면 효율 : 인접 행렬 방식(낭비 심함) < 인접 리스트 방식
* 속도 측면 : 인접 행렬 방식 > 인접 리스트 방식 (연결된 데이터를 하나씩 확인해야 한다)

DFS의 동작 과정

1.

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

2.

스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면,

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

3.

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

* DFS는 번호가 낮은 순서부터 처리하도록 구현한다. (관행적으로) *

 

 DFS 특징

> 동작 특성상 프로그램 수행시간이 느려질 수 있다.
> BFS보다 느리다.

 

#Ex2 DFS
'''
1. 시작 노드 방문 처리
2. 시작 노드와 연결되어 있는 노드들을 번호가 낮은 순서대로 탐색을 먼저 시작한다.
3. 만약 현재 노드가 방문처리가 되어있는 노드가 아니라면 더 깊이 탐색 시작(재귀함수 발동!)
'''
def dfs(graph,v,visited): # v는 시작노드
    visited[v]=True #True일 경우, 방문처리한 것
    print(v,end=' ')
    for i in graph[v]:
        if not visited[i]:
            dfs(graph,i,visited)
graph=[
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8]
    [1,7]
]

visited=[False]*9 # 방문처리 리스트
dfs(graph,1,visited)

---

[2] BFS

 

-> 너비 우선 탐색 (가까운 노드부터 알고리즘)
- 선입선출 방식인 큐 자료구조 방식을 사용한다.

* BFS 동작 방식

1.

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

2.

큐에서 노드를 꺼내서 해당 노드의 인접 노드 중에서

방문하지 않은 노드를 모두 큐에 삽입하고 방문처리함

3.

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

---

deque란?

> double-ended queue의 줄임말로,

양방향에서 데이터 처리가 가능한 queue형 자료구조

1. append(x)

: 오른쪽에 데이터 추가해주는 메소드

2. appendleft(x)

: 왼쪽(앞쪽)에서 추가해주는 메소드

3. extend(iterable)

: iterable argument를 오른쪽(마지막)에 추가해주는 메소드
iterable argument는 각 요소를 하나씩 반환 가능한 object를 의미한다.

list1=['a','b','c']
list2=['a','b','c']
list1.append('ef') >> ['a','b','c','ef']
list2.extend('ef') >> ['a','b','c','e','f']

4. extendleft(iterable)

: appendleft()와 마찬가지로 왼쪽에서 데이터 추가

5. pop()

: 오른쪽에서부터 차례대로 제거와 반환을 하는 메소드

6. popleft()

: 왼쪽에서부터 차례대로 제거와 반환을 하는 메소드

7. rotate(n)

: 요소들을 값만큼 회전해주는 메소드, 음수면 왼쪽으로 회전, 양수면 오른쪽으로 회전
rotate(1)이면 오른쪽으로 1칸씩 밀리는 거

 

# Ex3
'''
1. 큐를 생성한다.
2. 시작 노드를 방문처리한다.
3. 큐가 빌때까지 아래과정을 반복한다.
    3.1 큐의 왼쪽에서 1개를 꺼낸다.
    3.2 방금 꺼낸 노드와 연결되어 있는 다른 노드들중에 방문처리되지 않은 노드가 있으면, 큐에 그 값을 넣고, 해당 노드는 방문처리를한다.
'''
def bfs(graph,start,visited):
    queue=deque([start]) #deque(['a', 'b', 'c', 'd', 'e'])
    visited[start]=True
    while queue: # BFS는 DFS와 다르게 아래 for문이 끝나도 큐에 값이 남아있으니까, 큐가 빌때까지 while문을 또 돌려줘야 함
        v=queue.popleft()
        print(v,end=' ')
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i]=True

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

visited=[False]*9 # 방문처리 리스트
dfs(graph,1,visited)