[Coding Test] 이코테 - DFS/BFS

1. 자료구초 기초

• 탐색 (search)

    - 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정

    - 대표적인 탐색 알고리즘 : DFS, BFS

• 자료구조 (data structure)

   - 데이터를 표현하고 관리하고 처리하기 위한 구조

• 스택 (stack)

  - 선입후출 (First In Last Out) 또는 후입선출 (Last In First Out) 구조  ex) 상자 쌓기

• 큐 (queue)

  - 선입선출 (First In First Out) 구조  ex) 대기 줄

  - 큐를 구현할 때는 collections 모듈에서 deque 자료구조를 활용

  - deque는 스택과 큐의 장점을 모두 채택하여 데이터 삭입/삭제 속도가 리스트 자료형에 비해 효율적

 📌 deque 구현 예제

from collections import deque

queue = deque()

queue.append(5) #삽입
queue.append(3)
queue.append(2)
queue.popleft() #삭제 : 가장 처음 들어온 5 삭제

print(queue) #먼저 들어온 순서대로 출력
print(queue.reverse()) #역순으로 바꾸고 출력

• 재귀함수 (recursive function)

  - 자기 자신을 다시 호출하는 함수

  📌 2가지 방식으로 구현한 팩토리얼 예제

#반복문 활용
def factorial_iterative(n):
    result = 1
    for i in range(1,n+1):
    	result *= i
    return result
    
#재귀함수 활용
def factorial_recursive(n):
    if n <= 1:
        return 1
    return n*factorial_recursive(n-1)

---

2. 탐색 알고리즘 DFS/BFS

• 그래프 표현 방식

 

  - 인접 행렬 (Adjacency Matrix) : 2차원 배열로 그래프의 연결 관계를 표현하는 방식

    ㄴ 연결이 되어있지 않은 노드 → INF (무한의 비용 선언)

    ㄴ 👎 노드 개수가 많을수록 불필요한 메모리 낭비 유발

	0	1	2
0	0	7	5
1	7	0	INF
2	5	INF	0

   📌 인접 행렬 방식 예제

INF = 99999999 #무한의 비용 선언
#2차원 리스트를 이용해 인접 행렬 표현
graph = [
    [0,7,5],
    [7,0,INF],
    [5,INF,0]]

 

  - 인접 리스트 (Adjacency List) : 리스트로 그래프의 연결 관계를 표현하는 방식

    ㄴ '연결 리스트' 구조를 이용하여 연결된 노드에 대한 정보 저장

    ㄴ 👍효율적인 메모리 사용 👎특정한 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 느림

   📌 인접 리스트 방식 예제

#행이 3개인 2차원 리스트로 인접 리스트 표현
graph = [[] for _ in range(3)]

#노드 0에 연결된 노드 정보 저장 (노드,거리)
graph[0].append((1,7))
graph[0].append((2,5))

#노드 1에 연결된 노드 정보 저장
graph[1].append((0,7))

# ... 노드 2

 

2-1. DFS (Depth-First Search, 깊이 우선 탐색)

  - 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

1	탐색 시작 노드를 스택에 삽입하고 방문 처리
2	스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문처리 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄
3	2번의 과정을 더 이상 수행할 수 없을 때까지 반복

   📌 DFS 예제

def dfs(graph,v,visited):
    #현재 노드를 방문처리
    visited[v] = True
    print(v, end=' ')
    #현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
    	if not visited[i]:
        	dfs(graph,i,visited)
            
graph = [[..]] #각 노드가 연결된 정보를 리스트 자료형으로 표현

visited = [False] * node_count
dfs(graph,1,visited)

 

2-2. BFS (Breadth First Search, 너비 우선 탐색)

  - 가까운 노드부터 탐색하는 알고리즘

  ㄴ 👍 일반적으로 DFS보다 짧은 수행시간

1	탐색 시작 노드를 큐에 삽입하고 방문 처리
2	큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리
3	2번의 과정을 더 이상 수행할 수 없을 때까지 반복

   📌 BFS 예제

from collections import deque

def bfs(graph,start,visited):
    #큐 구현을 위해 deque 라이브러리 사용
    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 = [[..]] #각 노드가 연결된 정보를 리스트 자료형으로 표현

visited = [False] * node_count
bfs(graph,1,visited)