이것이 코딩테스트다 4일차 - BFS, DFS

1. 일단 자료구조 기초

• 탐색 : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정

• 자료구조 : 데이터를 표현하고 관리하고 처리하기 위한 구조

중요한 자료구조

• 스택 - DFS / python : list - append와 pop모두 맨 뒤가 기준이라(맨 뒤에 삽입, 맨 뒤 부터 출력)
• 큐 - BFS / python : deque (list로 큐를 구현하면 시간복잡도가 높음 - pop이 원소를 꺼낸 후에 이동 함)

중요한 함수

• 재귀함수 - 컴퓨터 메모리 - 스택 자료구조 - 종료조건 반드시 명시

2. 탐색 알고리즘

DFS동작 기본 - 재귀, 스택, 그리디

1. 조건에 맞는 인접노드의 인접노드 계속 방문, 방문처리, 스택에 쌓음.
2. 방문할 노드가 없으면 최상단 노드를 스택에서 제거, 그 다음 노드의 인접노드 방문, 방문처리, 스택에 쌓음
3. 반복

보통 번호가 낮은 순서부터 처리하도록 명시되어있다.

그래프 표현

• 인접 행렬(2차원 배열의 그래프) : 연결 되어있지 않은 노드 끼리는 무한 비용으로 작성

INF = 999999999 #무한 비용 선언

#2차원 행렬 만들기
graph = [[0,7,5],[7,0,INF],[5,INF,0]]

print(graph)

• 인접 리스트

파이썬에서는 C에서 처럼 구현하지 않아도 list에서 배열과 연결리스트 기능 모두 기본으로 제공한다. 단순히 2차원 리스트를 이용하면 된다.

#Row가 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에 연결된 노드 정보 저장(노드,거리)
graph[2].append((0,5))

print(graph)

메모리측면 : 당연히 인접 리스트가 좋다.
속도 : 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 느리다. 연결된 데이터를 하나씩 확인해야 하기 때문이다.

예를 들어 1과 7이 연결되어있는지 확인하기 위해서는

1. 인접행렬 : graph[1][7]확인
2. 인접리스트 인덱스 1인 리스트에서 순회해야 한다.

DFS 구현

#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)

#각 노드가 연결된 정보를 리스트 자료형으로 표현 (2차원 리스트)
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)

BFS동작 기본 - 큐, 최단경로

1. 탐색 시작 노드를 큐에 삽입, 방문처리
2. 큐에서 탐색한 노드를 꺼내고, 꺼낸 노드의 인접노드 중 방문하지 않은 노드를 모두 큐에 삽입, 방문하고 방문 처리
3. 반복

Deque 라이브러리 사용

from collections import deque

queue = dequeue()

#queue 구현
queue.append(1) #뒤에서 삽입
queue.popleft() #앞에서 출력

탐색을 수행할 때 deque는 O(N)의 시간이 소요
일반적이 경우 수행시간은 DFS보다 좋은 편

BFS구현

from collections import deque

#BFS메서드 정의
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

#각 노드가 연결된 정보를 리스트 자료형으로 표현 (2차원 리스트)
graph = [ [], [2,3,8],[1,7],[1,4,5],[3,5],[3,4],[7],[2,6,8],[1,7]]

#각 노드가 방문된 정보를 리스트 자료형으로 표현
visited = [False]*9

bfs(graph, 1, visited)