DFS와 BFS는 그래프 탐색 방식임
인접리스트와 인접행렬
그래프를 코드 상에서 표현하는 방식
인접행렬
graph = [[0, 1, 1, 1],
[1, 0, 0, 1],
[1, 0, 0, 1],
[1, 1, 1, 0]]- 행과 열이 연결된 노드를 의미
- 0, 1의 노드가 연결되어 있는 경우,
adjArray[0][1] = 1로 표시 - 즉 0번째 노드와 1번째 노드가 연결되었다면, 0행 1열에 1을 입력하고, 입력되지 않았다면 0을 입력하는 것
- 무향 그래프일 경우 대각선 대칭이지만, 유향그래프일 경우에는 대각선 대칭이 아님
- 가중치 그래프의 경우에는 1이 아닌 다른 값을 넣음으로써 가중치를 표현할 수 있음
장점 :
구현이 비교적 간단하다.
i, j노드의 연결을 확인할 경우 adjArray[i][j]로 바로 확인할 수 있어, O(1)의 시간복잡도를 가진다.단점 :
i 노드에 연결된 모든 노드를 확인하고자 할때 adjArray[i][0] ~ adjArray[i][N-1] 모두 확인해야해서
O(N)의 시간복잡도를 가진다. 노드가 많고 간선(연결)이 적을때 비효율이다.
공간복잡도도 O(N^2)로 메모리를 많이 차지한다.인접리스트
graph = [
[1, 2, 3],
[0, 3],
[0, 3],
[0, 1, 2]
]- 연결된 노드 자체가 들어가 있음
- 각각의 인덱스에 헤당하는 노드에 연결된 노드들을 리스트형태로 저장
- 노드를 문자열로 나타내었을 때 Dictionary를 활용할 수 있어서 편리
graph_list = {1: set([3, 4]),
2: set([3, 4, 5]),
3: set([1, 5]),
4: set([1]),
5: set([2, 6]),
6: set([3, 5])}- 가중치 그래프에서 가중치를 표현하기 위해서 연결정보에 튜플형태나 다른 방식으로 가중치를 추가적으로 입력해야
장점 :
i와 연결된 모든 노드를 확인하고자 할때 최악의 경우(i가 모든 노드와 연결된 경우) O(N)이지만,
대부분의 경우 항상 O(N)인 인접행렬보다 빠르다.
공간복잡도도 간선의 개수를 E라 할때 최악의 경우를 제외하고 O(E) < O(N^2)이므로 낭비가 적다.단점 :
i, j의 연결을 확인하고 싶을때 adjList[i]를 순회하며 j가 있는지 봐야 하므로 O(N)으로 인접행렬보다 느리다.DFS
대다수의 코딩테스트에서 구현
주로 스택 또는 재귀로 구현
백트래킹을 할 때 쓰임
원칙 : "앞으로 가야 할 노드", "이미 방문한 노드"
백트래킹
백트래킹은 해결책에 대한 후보를 구축해나가다 가능성이 없다고 판단되는 즉시 후보를 포기
왔던 길을 되돌아가 다른 길을 바로 찾음
DFS는 백트래킹의 골격을 이루는 알고리즘
주로 재귀로 구현
가보고 되돌아오는 것을 반복
최악의 경우에는 모든 경우를 다 거치므로 브루트포스와 유사
제약 충족 문제 풀이 시 필수적인 알고리즘
휴리스틱과 조합 탐색 같은 개념을 함께 결합해 문제 풀이
제약 충족 문재
수많은 제약 조건을 충족하는 상태를 찾아내는 문제
백트래킹을 하면서 가지치기를 통해 최적화 가능
ex. 스도쿠, 십자말 풀이, 8퀸 문제, 4색 문제 같은 퍼즐문제
ex2. 배낭 문제, 문자열 파생, 조합 최적화 문제 등
BFS
주로 큐로 구현
그래프의 최단 경로를 구하는 문제 등에 사용됨
다익스트라 알고리즘으로 최단 경로를 찾는 문제에서 BFS로 구현 가능
왜 그래프의 최단 경로를 구하는 문제에서 BFS 사용할까
F 를 처음 방문한 그 순간이 F 를 가장 빠르게 찾은 것이다.
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]
]
# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9
# 정의된 DFS 함수 호출
dfs(graph, 1, visited)인접행렬, 재귀함수
# Function to perform DFS on the graph
def DFS(self, start, visited):
# Print current node
print(start, end = ' ')
# Set current node as visited
visited[start] = True
# For every node of the graph
for i in range(self.v):
# If some node is adjacent to the
# current node and it has not
# already been visited
if (Graph.adj[start][i] == 1 and
(not visited[i])):
self.DFS(i, visited)인접리스트, stack 자료구조
def iterative_dfs(start_v):
visited = []
stack = [start_v]
while stack:
v = stack.pop()
if not visited[v]:
visited.append(v)
for w in graph[v]:
stack.append(w)
return discovered
인접행렬, stack 자료구조
n, m, v = map(int, input().split())
matrix = [[0] * (n+1) for _ in range(n+1)]
visited = [False] * (n+1)
for _ in range(m):
f, t = map(int, input().split())
matrix[f][t] = matrix[t][f] = 1
def dfs(matrix, i, visited):
stack=[i]
while stack:
value = stack.pop()
if not visited[value]:
print(value, end=' ')
visited[value] = True
for c in range(len(matrix[value])-1, -1, -1):
# 문제에서 작은 숫자부터 입력하기를 요구해서 반대로 순회했습니다.
# 순차적으로 하면 스택에 2,3,4 순으로 입력되고 4부터 pop되어
# 가장 큰 수인 4부터 pop되기 때문입니다.
if matrix[value][c] == 1 and not visited[c]:
stack.append(c)
dfs(matrix, v, visited)BFS 기본 구조
인접리스트, queue 자료구조
from collections import deque
# BFS 함수 정의
def bfs(graph, start, visited):
# 큐(Queue) 구현을 위해 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]
]
# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9
# 정의된 BFS 함수 호출
bfs(graph, 1, visited)인접행렬, queue 자료구조
n, m, v = map(int, input().split())
matrix = [[0] * (n+1) for _ in range(n+1)]
visited = [False] * (n+1)
for _ in range(m):
f, t = map(int, input().split())
matrix[f][t] = matrix[t][f] = 1
from collections import deque
def bfs(matrix, i, visited):
queue= deque()
queue.append(i)
while queue:
value = queue.popleft()
if not visited[value]:
print(value, end=' ')
visited[value] = True
for c in range(len(matrix[value])):
if matrix[value][c] == 1 and not visited[c]:
queue.append(c)다른 BFS 풀이
https://www.acmicpc.net/problem/16953
import sys
input = sys.stdin.readline
from collections import deque
a, b = map(int, input().split())
queue = deque([(a, 1)]) # 큐에 (현재 숫자, 연산 횟수) append
res = -1
while queue:
until, cnt = queue.popleft()
# 숫자가 목표 숫자와 동일해지면 while문 끝내기
if until == b:
res = cnt
break
# 2를 곱했을 때 b보다 크면 큐에 넣지 않음 => 이하이면 큐에 넣음
if until * 2 <= b:
queue.append((until*2, cnt+1))
# 오른쪽에 1을 더했을 때 b보다 크면 큐에 넣지 않음 => 이하이면 큐에 넣음
if int(str(until) + "1") <= b:
queue.append((int(str(until) + "1"), cnt+1))
print(res)Ref.
그게, 할 수 있다고 믿어야 해