[알고리즘] BFS(넓이 우선 탐색) / DFS(깊이 우선 탐색)

• 인접 행렬 : 2차원 배열로 그래프의 연결 관계를 표현하는 방식
  • 간선 정보를 저장하기 위해 O(V^2)만큼의 메모리 공간 필요
  • 특정한 노드 A에서 다른 특정한 노드 B로 이어진 간선의 비용 : O(1)
  • V : 노드

  0 1 2   #노드 번호
0 0 7 5   #거리
1 7 0 ~
2 5 ~ 0

• 인접 리스트 : 리스트로 그래프의 연결 관계를 표현하는 방식
  • 간선 정보를 저장하기 위해 O(E)만큼의 메모리 공간 필요
  • 특정한 노드 A에서 다른 특정한 노드 B로 이어진 간선의 비용 : O(V)
  • E : 간선

graph = [[] for _ in range(노드개수)]

graph[0].append((노드번호, 노드거리))
graph[0].append((노드번호, 노드거리))

graph[1].append((노드번호, 노드거리))
...

---

BFS(넓이 우선 탐색)

• 시간 복잡도 : O(V+E)
• 하나의 경우의 수에 대한 다음 단계의 모든 경우의 수를 조사하면서 해를 찾는 과정
• 정점들과 같은 레벨에 있는 노드들 (형제 노드들)을 먼저 탐색하는 방식
• 동작 방식
  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]]   #1~8 순서대로 인접한 노드 적기

visited = [False] * 9   #노드개수+1

bfs(graph, 1, visited)

 

[예 - 최단경로 찾기]

1. 거리가 0인 개수 : 1. 정답이 아님 → 거리가 0인 개수 : 0
2. 거리가 1인 개수 : 2, 5, 6. / 2가 정답이 아님 → 3, 11을 큐에 추가, 거리가 1인 개수 : 2 / 반복...

while len(queue) > 0:   #큐에 데이터가 있다면
	count = len(queue)   #같은 거리에 있는 큐 데이터 개수
	for time in range(count):   #같은 거리에 있는 큐 개수 만큼 검사
		now = queue.pop(0)
		if now == dest:   #정답이 존재하면 값 반환
			return answer
		for i in data:   #연결된 포인트 완전 탐색
			if i[0]==now and visited[i[1]-1]==False:   #방문하지 않은 연결된 길이라면 큐에 추가하고 방문 표시
				queue.append(i[1])
				visited[i[1]-1]=True
			elif i[1]==now and visited[i[0]-1]==False:
				queue.append(i[0])
				visited[i[0]-1]=True
	answer += 1   #거리를 1 더 벌림
return answer

 

DFS (깊이 우선 탐색)

• 거리가 1인 개수 : 2, 5, 6. / 2가 정답이 아님 → 3, 11을 큐에 추가, 거리가 1인 개수 : 2 / 반복...
• 정점의 자식들을 먼저 탐색하는 방식
• 시간 복잡도 : O(V+E)
• 동작 과정
  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)

graph = [[],[2,3,8],[1,7],[1,4,5],[3,5],[3,4],[7],[2,6,8],[1,7]]   #1~8 순서대로 인접한 노드 적기

visited = [False] * 9   #노드개수+1

dfs(graph, 1, visited)

 

[예 - 미로 찾기]

1. 배열로 선언
2. [0,0]에서 흰색으로 갈 수 있는 값 [0,1]을 찾음
3. [0,1]에서 흰색으로 갈 수 있는 값 [0,2], [1,1]을 찾음... 반복

stack = [[0,0]]
dest = [5,5]
hori = 6
verti = 6

while len(stack)>0:   #스택에 데이터가 있다면
	now = stack.pop()   
	if now == dest:   #정답 여부 검사
		return True
	x = now[1]
	y = now[0]
	if x-1 > -1:   #왼쪽으로 이동할 수 있다면
		if maps[y][x-1]==0:   #스택에 추가하고 방문 여부를 2로 표시
			stack.append([y,x-1])
			maps[y][x-1]=2
	if x+1 < hori:   #오른쪽으로 이동할 수 있다면
		if maps[y][x+1]==1:
			stack.append([y,x+1])
			maps[y][x+1]=2
	if y-1 > -1:   #위로 이동할 수 있다면
		if maps[y-1][x]==1:
			stack.append([y-1, x])
			maps[y-1][x]=2
	if y+1 < verti:   #아래로 이동할 수 있다면
		if maps[y+1][x]==1:
			stack.append([y+1,x])
			maps[y+1][x]=2
return False   #스택에 데이터가 없으면 False