[이것이 코딩테스트다] 3. DFS/BFS

1. 그래프 탐색 알고리즘

- 탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말한다.

- DFS와 BFS는 코딩테스트에서 매우 자주 등장하는 유형.

 

2. 스택 자료구조

- 먼저 들어온 데이터가 나중에 나가는 형식(선입후출)의 자료구조이다.

- 입구와 출구가 동일한 형태로 스택을 시각화 함.

+ 파이썬에서 구현 : list 활용. append(), pop()을 이용해 삽입, 삭제 할 수 있음. 최상단 원소부터 출력하고자 하면 [::-1]

 

3. 큐 자료구조

- 먼저 들어온 데이터가 먼저 나가는 형식(선입선출)의 자료구조이다.

- 입구와 출구가 모두 뚫려 있는 터널과 같은 형태로 시각화 함.

+ 파이썬에서 구현 : 리스트를 활용할 수도 있으나 시간 복잡도가 높아져 collections 모듈의 deque 함수를 이용.

from collection import deque

queue = deque()

queue.append()
queue.popleft()

queue.reverse() #역순으로 바꾸기. 나중에 들어온 원소부터 출력

 

4. 재귀 함수 : 자기 자신을 다시 호출하는 함수

- 단순한 형태의 재귀함수 예제 : 문자열 무한히 출력합니다. 어느정도 출력하다가 최대 재귀 깊이 초과 메시지가 출력됩니다.

def recursive_function():
	print("재귀 함수를 호출합니다.")
    recursive_function()

+ 마치 스택 자료구조처럼 마지막 들어온 결과가 가장 최신으로 쌓임.

 

- 재귀 함수의 종료 조건 : 의도적으로 무한루프를 이용하지 않는 경우 종료 조건을 반드시 명시해야 함.

: 종료 조건을 포함한 재귀 함수 예제

def recursive_function():
	if i == 100 :
    	return 
        
	print(i,"번째 재귀 함수 에서", i+1,"번째 재귀 함수를 호출합니다.")
    recursive_function(i+1)
    print(i,"번째 재귀 함수를 종료합니다.")
    
recursive_function(1)

 

- 팩토리얼 재귀적으로 구현하기.

def factorial_reCursive(n):
    if n<=1:
        return 1
    return n * factorial_reCursive(n-1)
    
factorial_reCursive(5)

 

- 유클리드 호제법(최대 공약수 계산)

 : 두 자연수 A, B, (A%B=)R. A와 B의 최대 공약수는 B와 R의 최대 공약수와 같다. (재귀 함수로 작성할 수 있음)

def GCD(a, b):
    if a%b == 0:
        return b
    else:
        return GCD(b, a%b)
        
GCD(192, 162)

 

- 재귀 함수 사용의 유의 사항

 + 복잡한 알고리즘을 간결하게. 단 어려운 형태의 코드가 될수 있음 주의.

 + 모든 재귀함수는 반복문으로 구현할 수 있음. 모든 반복문도 재귀함수로 구현 가능.

 + 컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓임 > 스택 라이브러리 대신 재귀함수 이용 가능.

 

---

5. DFS (Depth-First Search)

- 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, visitied)
            
            
graph = [
    [],
    [2, 3, 8], #첫 노드와 연결된 노드 번호 표현
    [1, 7], #두번째 노드와 연결된 노드 번호...
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

# 각 노드가 방문된 정보를 표현
visited = [False] * 9

#정의된 DFS 함수 호출
dfs(graph, 1, visited)

 

---

6. BFS (Breadth-First Search)

 - BFS는 너비 우선 탐색. 가까운 노드부터 우선 탐색.

 - 큐 자료구조 이용.

 - 동작 과정

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

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

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

 + 최단거리 구할 때 자주 사용됨.

from collections import deque

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
                
graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

# 각 노드가 방문된 정보를 표현
visited = [False] * 9

# 정의된 BFS 함수 호출
bfs(graph, 1, visited)