출처: www.youtube.com/watch?v=7C9RgOcvkvo
그래프 탐색 알고리즘: DFS/BFS
탐색이란 많은양의 데이터 중에서 원하는 데이터를 찾는 과정
조건에 맞는 거 위치 찾기 등
<스택 자료구조>
LIFO(선입후출, 먼저 들어 온 데이터가 나중에 나감)
- 입구와 출구가 동일하다.
ex. 박스 쌓기
#stack
stack = []
stack.append(5)
stack.append(2)
stack.pop()
stack.append(1)
print(stack[::-1]) #최상단 원소부터 출력
print(stack) #최하단 원소부터 출력append method와 pop method를 사용함 -> 두 함수 모두 시간복잡도가 O(1)
<큐 자료구조>
FIFO(선입선출, 먼저 들어온 데이터가 먼저 나감)
- 입구와 출구가 모두 뚫려 있는 터널과 같은 형태
ex) 대기열, 은행 대기 등
#queue
queue = []
queue.append(5)
queue.append(2)
queue.pop(0)
queue.append(3)
queue.pop(0)
print(queue) # 처음부터# deque 이용
from collections improt deque
queue = deque()
queue.append(5)
queue.append(2)
queue.popleft()
queue.append(3)
queue.popleft()
print(queue) # 먼저 들어온 순서대로
queue.reverse() # 역순
print(queue) # 늦게 들어온 순서대로리스트를 사용하는 것보다 deque를 이용하는 것을 추천
-> 리스트를 사용하여 큐를 구현하는게 deque보다 시간복잡도가 높다
-> 효율적인 측면에서 list를 사용하는건 좋지 않음
<재귀함수>
재귀함수: 자기 자신을 다시 호출하는 함수
dfs구현시 자주 사용된다.
재귀함수 사용시 최대 깊이 제한에 주의해야함
수학적 점화식을 구현한다.
"재귀함수의 종료 조건"
- 재귀 함수의 종료 조건은 반드시 명시 되어야 함(ex. 100번째 호출시 종료 등)
- 종료 조건을 제대로 명시하지 않으면 함수가 무한히 호출될 수 있음
stack처럼
ex. 팩토리얼, 최대 공약수 계산(유클리드 호제법) 등
+) 0!= 1, 1! = 1
+) 유클리드 호제법
-> 두 개의 자연수에 대한 최대 공약수 구하기 문제
: 두 자연수 A, B에 대하여 (A>B) A를 B로 나눈 나머지를 R이라고 하자
이 때 A와 B의 최대공약수는 B와 R의 최대공약수와 같다
=> GCD(A, B) == GCD(B, A%B)
def gcd (a, b):
if a%b == 0:
return b
else:
return gcd(b, a%b)
"유의사항"
- 재귀함수를 잘 활용하면 복잡한 알고리즘을 간결하게 작성할 수 있다.
단) 다른 사람이 이해하기 어려운 형태의 코드가 될 수도 있으므로 신중하게 사용해야 한다.
- 모든 재귀함수는 반복문을 이용하여 동일한 기능을 구현할 수 있다.
- 재귀함수가 반복문보다 유리한 경우도 있고 불리한 경우도 있음
- 컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부에 스택 프레임에 쌓임
=> 그래서 스택을 사용해야할 때 구현상 스택 라이브러리 대신에 재귀 함수를 이용하는 경우가 많음
<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)
# 각노드가 연결된 정보 표현(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)
//c++
bool visited[9];
vector<int> graph[9];
void dfs(int x){
visited[x] = true;
cout << x << " ";
for(int i=0; i < graph[x].size(); i++){
int y= graph[x][i];
if(!visited[y]) dfs(y);
}
}
<DFS를 활용하는 알고리즘>
- 음료수 얼려 먹기
1. 특정한 지점의 주변 상, 하, 좌, 우를 살펴본 뒤에 주변 지점 중에서 값이 '0'이면서 아직 방문하지 않은 지점이 있다면 해당 지점을 방문
2. 방문한 지점에서 다시 상, 하, 좌, 우를 살펴보면서 방문을 진행하는 과정을 반복하면, 연결된 모든 지점을 방문할 수 있다.
3. 모든 노드에 대해 1~2번 과정을 반복하며, 방문하지 않은 지점의 수를 카운트한다.
#음료수 얼려 먹기
def dfs(x, y): #dfs로 특정 노드를 방문하고 연결된 모든 노드들도 방문
if x<=-1 or x>=n or y <=-1 or y>=m: #주어진 범위 벗어나는 경우 종료
return False
if graph[x][y] == 0: #현노드를 아직 방문하지 않았다면
graph[x][y] = 1 #방문처리
#상하좌우 모두 재귀적 호출
dfs(x-1, y)
dfs(x, y-1)
dfs(x+1, y)
dfs(x, y+1)
return True
return False
n, m = map(int, input().split())
graph = []
for i in range(n):
graph.append(list(map(int, input)))
result = 0
for i in range(n):
for j in range(m):
if (dfs(i, j) == True:
result+=1
print(result)<BFS(Breadth-First Search)>
- 너비 우선 탐색, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘
- 큐 자료구조 이용하여 구현
1. 탐색 시작 노드를 큐에 삽입하고 방문처리
2. 큐에서 노드를 꺼낸뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리
3. 더 이상 2번의 과정을 수행할 수 없을때까지 반복
- 간선이 동일한 상황에서 최단 거리를 찾는 목적으로도 사용됨
#Python BFS
from collections import deque
def bfs(graph, start, visited):
queue = deque([start]) #큐 구현을위한 deque 라입르ㅓ리
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(graph, 1, visited)#C++ BFS
bool visited[9];
vector<int> graph[9];
void bfs(int start){
queue<int> q;
q.push(start);
visited[start] = true;
while(!q.empty(){
int x = q.front();
q.pop();
cout<< x << " ";
for(int i=0; i < graph[x].size();i++){
int y = graph[x][i];
if(!visited[y]){
q.push(y);
visited[y] = true;
}
}
}
}
<BFS를 활용하는 알고리즘>
- 미로 탈출
1. 시작 지점에서 가까운 노드부터 차례대로 모든 노드를 탐색
2. 상, 하, 좌, 우로 연결된 모든 노드로의 거리가 1로 동일
-> 따라서 (1,1) 지점부터 BFS를 수행하여 모든 노드의 최단 거리 값을 기록하면 해결할 수 있음
- 방문시 누적 거리(이전 값 + 1)로 값을 바꾸어 준다.
from collections import deque
def bfs(x, y):
queue = deque()
queue.append((x, y))
while queue: #큐가 빌때까지 반복
x, y = queue.popleft()
#4방향
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
#범위를 벗어난 경우
if nx <0 or nx >=n or ny < 0 or ny >=m:
continue
#벽인 경우
if graph[nx][ny] = 0:
continue
#해당 노드를 처음 방문하는 경우에만 최단 거리 기록
if graph[nx][ny] == 1:
graph[nx][ny] = graph[x][y] + 1
queue.append((nx, ny))
#가장 오른쪽 아래까지의 최단 거리 반환
return graph[n-1][m-1]
n, m = map(int, input().split())
grpah = []
for i in range(n):
graph.append(list(map(int, input())))
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
prnit(bfs(0, 0))