2020/03/04 - [공부/알고리즘] - [알고리즘 자습]그래프(Graph) - 1. BFS(너비우선탐색)의 정의와 활용, 예제, 파이썬(Python3)
[알고리즘 자습]그래프(Graph) - 1. BFS(너비우선탐색)의 정의와 활용, 예제, 파이썬(Python3)
코딩테스트를 준비하는 사람이든 아니든, 프로그래밍에 발을 들여본 적이 있는 사람들은 무조건 들어봤을 것이다. 너비 우선 탐색, BFS이다. 코딩테스트 단골 문제이기도 하고, 백준 및 프로그래머스에서도 굉장히..
sexy-developer.tistory.com
위의 링크를 걸어놓은 이전 게시물에서, 그래프 순회 알고리즘을 배워야 하는 이유, 그리고 최단 경로 등의 문제에 주로 쓰이는 BFS에 대해 알아보고, 예제를 풀어봄으로써 그 원리를 익혔다. 이번 게시물에는 DFS의 정의, 활용, 예제를 풀면서 DFS에 대한 내용을 정리하겠다. 얼추 개념은 알지만, 코드로 구현해서 문제를 푸는데 자신감이 없는 사람은 나와 같이 공부해보자.
DFS(너비 우선 탐색)
BFS와 마찬가지로, DFS 또한 그래프 순회 알고리즘이다. 즉, 하나의 그래프에서 갈 수 있는 모든 노드들을 차례대로 순회하는 알고리즘이라는 말이다. BFS와 다른 것은 첫째, 방문 순서가 다르다는 점이다. 이는 아래 그림을 보면 알 수 있다.
위의 이미지처럼, 하나의 노드에서 갈 수 있는 곳까지 쭉 갔다가, 더 이상 갈 수 있는 노드가 없다면 이전 노드로 돌아와서 다시 갈 수 있는 노드를 찾는다. bfs와는 다른 방문 순서를 갖는다. 위의 애니메이션을 말로 풀어서 설명하자면, 아래와 같다.
- 시작 정점 1을 stack에 넣는다.
- stack에 원소가 있는 동안, 아래의 과정을 반복한다.
- stack에 있는 원소를 pop해서 temp라는 변수에 저장한다
(stack은 LIFO 구조이기 때문에, 가장 최근에 스택에 넣은 원소가 나오게 된다.) - vistied[temp]를 True로 만들어줌으로써, node를 방문했다고 표시한다.
- temp에서 갈 수 있는 노드들 중 아직 방문하지 않은 노드들을 stack에 집어넣는다.
- stack에 있는 원소를 pop해서 temp라는 변수에 저장한다
두번째 bfs와의 다른 점은 dfs는 재귀적은 방법으로 실행할 수 있다는 점이다. 실제로, 연습을 한다면 반복적인 방법으로dfs를 짜는 것보다 훨씬 더 간결하게 코드를 짤 수 있다.
여기까지가 DFS에 대한 아주 개략적인 설명이고, 이를 예제를 풀어봄으로써 익혀보자.
예제1: 주어진 그래프를 DFS로 순회하기
입력
- 그래프의 인접 행렬
[[1, 1, 1, 1, 0, 0],
[1, 1, 0, 0, 0, 0],
[1, 0, 1, 0, 0, 1],
[1, 0, 0, 1, 1, 0],
[0, 0, 0, 1, 1, 0],
[0, 0, 1, 0, 0, 1]]
- 시작 정점
출력
- 그래프를 방문하는 순서
정답
- [0, 3, 4, 2, 5, 1] 혹은
- [0, 1, 2, 5, 3, 4]
답안 1: 반복문을 활용한 DFS
정말 기본적인 DFS이다. 아래 코드를 보자. 아래 코드는 반복문을 활용해서 구현한 예이다.
# 그래프를 반복적으로 dfs함
def iterative_dfs_desc(graph, input_start):
visited = [0] * len(graph)
answer = []
stack = [input_start]
while stack:
print("\nstack: ", stack)
temp = stack.pop()
print("pop된 노드: ", temp)
visited[temp] = 1
answer.append(temp)
for i in range(len(graph[temp])):
if graph[temp][i] == 1 and visited[i] == 0 and temp != i:
stack.append(i)
return answer
graph = [[1, 1, 1, 1, 0, 0],
[1, 1, 0, 0, 0, 0],
[1, 0, 1, 0, 0, 1],
[1, 0, 0, 1, 1, 0],
[0, 0, 0, 1, 1, 0],
[0, 0, 1, 0, 0, 1]]
start = 0위 코드를 실행하면 아래와 같은 결과가 나온다.
우리가 원하던 대로, 결과가 나온 것을 알 수 있다. 이제 이 코드에 있는 print문을 통해서, 각 단계마다 dfs가 어떻게 진행되고 있는 지를 알아보자. 그러기 위해서, 반복을 앞둔 stack을 출력해볼 것이다. 그리고, stack에서 pop되는 노드를 출력해서 어느 노드를 방문했는지를 확인할 것이다.
콘솔 창에는 위와 같은 결과물이 출력된다. 이제, 표를 통해 각 단계가 어떻게 진행되는지 알아보지.
dfs의 과정을 나타낸 표이다. 이 표를 보면 dfs가 어떻게 흘러가는 지 알 수 있다.
* 노드의 방문 순서를 오름차순, 내림차순으로 출력해야 할 때가 있다. 위의 경우는 방문할 수 있는 노드가 [1. 2. 3] 일 경우 3부터 방문한다. 이를 수정하고 싶다면, while문 내부의 for문을 아래와 같이 수정하면 된다.
for i in range(len(graph[temp]) - 1, -1, -1):
if graph[temp][i] == 1 and visited[i] == 0 and temp != i:
stack.append(i)위에도 말했다시피, 이는 반복문을 활용한 답안이다. 그러나 우리는 코드의 간결성을 위해서 재귀를 활용할 수도 있다. 재귀로도 풀어보자. 만약 재귀함수가 뭔지 모르겠다면, 아래 링크를 달아놓을테니 공부를 해보시길 바란다.
2020/02/06 - [공부/알고리즘] - [알고리즘 자습]재귀(recursive) 함수 - N까지의 합, 거듭제곱, 구구단, 팩토리얼 등 예제- Python3
[알고리즘 자습]재귀(recursive) 함수 - N까지의 합, 거듭제곱, 구구단, 팩토리얼 등 예제- Python3
알고리즘을 공부하는 사람은 누구나 한번쯤 재귀함수에 대해 들어봤을 것이다. 그러나, 재귀적인(recursive) 방법은 코드가 직관적이긴 하나, 디버깅이 힘들고, 그 아이디어를 짜는 것이 생각보다 힘들다보니 보통..
sexy-developer.tistory.com
답안 2: 재귀호출을 활용한 DFS
# 재귀함수
def recurse(graph, start, visited, answer):
# print(start, "방문")
visited[start] = 1
answer.append(start)
for i in range(len(graph[start])):
if graph[start][i] == 1 and visited[i] == 0 and start != i:
recurse(graph, i, visited, answer)
# 재귀함수를 이용한 풀이
def recursive_dfs(graph, input_start):
visited = [0] * len(graph)
answer = []
recurse(graph, input_start, visited, answer)
return answer
graph = [[1, 1, 1, 1, 0, 0],
[1, 1, 0, 0, 0, 0],
[1, 0, 1, 0, 0, 1],
[1, 0, 0, 1, 1, 0],
[0, 0, 0, 1, 1, 0],
[0, 0, 1, 0, 0, 1]]
start = 0위 코드를 실행하면, 아래와 같은 결과가 나온다.
반복을 이용한 dfs와 그 흐름이 크게 다르지 않으므로, 이에 대한 설명은 생략하겠다. 다만, 재귀로 짜는 것이 훨씬 간결하다. 시작 정점에 대해 재귀호출을 하고, 호출한 노드번호에 대해서 조건을 만족하는(아직 방문하지 않았고, 인접하고 있는) 노드들을 찾으면 그 노드에 대해 재귀호출하면 된다.
예제2: 주어진 그래프를 DFS로 순회하면서, 시작 정점에서 리프 노드까지 갈 수 있는 모든 경로 출력하기
문제
- 시작 노드에서, 더이상 갈 수 있는 노드가 없을 때까지 쭉 갔을 때 포함된 노드들의 순서를 경로라 한다.
- 위의 경우, 가능한 모든 경로는 [1, 0, 2, 5, 6], [1, 0, 3, 4], [1, 0, 3, 7] 이다.
- 모든 경로를 출력하라
입력
- 그래프의 인접 행렬
[[0, 1, 1, 1, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 1, 0, 0],
[1, 0, 0, 0, 1, 0, 0, 1],
[0, 0, 0, 1, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 1, 0],
[0, 0, 0, 0, 0, 1, 0, 0],
[0, 0, 0, 1, 0, 0, 0, 0]]
- 시작 정점
출력
- 시작 노드에서 출발해서, 더이상 인접한 노드가 없을 때 까지의 가능한 모든 경로를 출력
- 인접 노드 중, 노드 번호가 낮은 노드부터 방문하라
DFS에서 응용을 두 스쿱쯤 더한 문제이다. 문제에서 추가로 고려할 점은, [1, 0, 3, 4]의 경로를 먼저 찾고 나서, 4를 pop하고 경로가 [1, 0, 3]이 된 상태에서, 7을 경로에 넣어서 [1, 0, 3, 7]을 만드는 것이다. 이는 백트래킹이라고 하는 기법인데, DFS의 흐름을 알고 있다면, 이 또한 어렵지 않다. 이 문제 또한 재귀, 반복 두 방법으로 풀어볼 것이다.
답안 1: 반복문을 이용한 풀이
# 반복적 DFS
def dfs_iterative(graph, input_start):
answer = []
start = input_start
stack = [start]
path = []
visited = [False] * len(graph)
for i in range(len(graph)):
for j in range(len(graph[i])):
if i == j:
graph[i][j] = 0
while stack:
print("\n")
print("stack: ", stack)
start = stack.pop()
print(start, "방문")
visited[start] = True
path.append(start)
print("path: ", path)
cands = []
for i in range(len(graph[start])-1,-1, -1):
if not visited[i] and graph[start][i] == 1:
cands.append(i)
print("인접한 노드: ", cands)
# 갈 수 있는 노드 있음
if cands:
stack.extend(cands)
else:
# 끝자락에 도착
print("끝자락 도착")
answer.append(copy.deepcopy(path))
while True and path:
print("빠진 노드: ", path.pop())
try:
temp = path[-1]
except:
return answer
arr = []
for i in range(len(graph[temp])-1, -1, -1):
if graph[temp][i] == 1 and not visited[i]:
arr.append(i)
if arr:
print("이제 그만 뺌")
break
else:
print("아직 pop해야함")
print("빠진 path: ", path)
print("\nanswer: ", answer)
return answer
graph = [[0, 1, 1, 1, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 1, 0, 0],
[1, 0, 0, 0, 1, 0, 0, 1],
[0, 0, 0, 1, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 1, 0],
[0, 0, 0, 0, 0, 1, 0, 0],
[0, 0, 0, 1, 0, 0, 0, 0]]
start = 1
print("반복 DFS 정답: ", dfs_iterative(graph, start))
코드에 프린트문이 너무 많아서 보기가 힘들다면, 글 마지막에 제거한 코드를 올릴테니 그것을 보기 바란다.
위의 코드에서 나오는 temp변수는, 그래프의 끝자락에 도착했을 때, 그때 까지 만들어진 path의 마지막 원소를 pop해서 저장한 것이다. 이 temp에서 갈수 있는 노드를 arr이라는 배열에 저장하고, arr에 원소가 있다면 그 노드를 방문한다. 그렇지 않고 arr에 원소가 없다면, 다시 path에서 마지막 원소를 pop한다. 이 과정을 반복한다(백트래킹).
그러다가, 더 이상 갈 수 있는 노드를 찾지 못하면, path의 원소의 갯수가 0이 되어 try문을 실행하지 못하고, except문의 return에 걸려 함수가 종료된다.
위 코드를 실행하면 아래와 같은 결과가 나타난다.
이렇게, 우리가 원하는 결과를 출력한다. 좀 더 자세히 알아보기 위해, 표를 살펴보자.
이 표를 위에서 아래로, 왼쪽에서 오른쪽으로 쭉 보다보면, 이 함수가 어떻게 흘러가는지 정말 잘 알 수 있다. 정말 열심히 만든 표이니깐 꼭 도움이 될거야. 그리고, 표를 쭉 보면서, 어떨 때 백트래킹을 시작하는지, 어떨 때 백트래킹이 종료되고 다음 반복을 실시하는지 그 흐름을 꼭 익히기 바란다.
답안 2: 재귀 호출을 이용한 풀이
이번엔 재귀호출을 이용해 가능한 모든 경로를 출력해보겠다.
# 재귀적 DFS
def recurse(graph, start, answer, path, input_start):
print("\n시작 노드: ", start)
path.append(start)
print("현재 path: ", path)
cands = []
# 갈 수 있는 노드 찾기
for i in range(len(graph[start])):
if i != start and graph[start][i] == 1:
cands.append(i)
# 갈 수 있는 노드가 없다면, 현재까지의 path를 answer의 원소로 저장하고, return하는 것으로 종료
if not cands:
answer.append(copy.deepcopy(path))
print("끝자락에 도착해서 종료, answer: ", answer)
print("빠질 노드: ", path.pop())
print("path: ", path)
return
# 갈 수 있는 노드가 있다면, 그 노드로 가는 경로에 해당하는 graph의 원소를 0으로 바꾸고, 재귀 호출
else:
print("후보노드: ", cands)
while cands:
cand = cands.pop(0)
graph[start][cand] = 0
graph[cand][start] = 0
recurse(graph, cand, answer, path, input_start)
# 반복이 끝났다는 것은 해당 노드에서 더이상 갈 수 있는 노드가 없다는 뜻. 따라서 path에서 pop한다.
print("반복 끝나고 빠질 노드: ", path.pop())
def dfs_recursive(graph, input_start):
path = []
answer = []
start = input_start
recurse(graph, start, answer, path, input_start)
return answer
graph = [[0, 1, 1, 1, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 1, 0, 0],
[1, 0, 0, 0, 1, 0, 0, 1],
[0, 0, 0, 1, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 1, 0],
[0, 0, 0, 0, 0, 1, 0, 0],
[0, 0, 0, 1, 0, 0, 0, 0]]
start = 1
print("\n재귀 DFS 정답: ", dfs_recursive(graph, start))
사실 재귀호출로 이문제를 진작에 풀었는데, 반복을 활용한 dfs도 연습해야 할 것 같아서, 답안 1에 나오는 코드를 작성했다. 재귀로 짜는게 훨씬 편했다. 반복으로 짜면 머리통 터질것같다. 물론 내가 아직 초보라서 그렇지만, 이글을 읽는 다른 사람들도 다 초보일 테니까 그냥 익숙지 않더라도 재귀로 짜는걸 추천한다.
위 코드를 실행하면 아래와 같은 결과가 나온다.
정말 훨씬 깔끔하다. 이로써 원하는 답을 재귀, 반복 2가지 방법을 사용해서 출력했다.
활용
bfs는 주로 최단 경로를 구하는 데 쓰인다. 시작 정점에서 출발해서, bfs를 쭉 해가면서, queue에 타겟이 들어오는 순간 bfs를 종료하는 방식으로 말이다.
dfs는 이와는 달리, 가능한 경로를 모두 구해서 비교해야 할때 등, 그래프의 끝자락에 있는 노드(리프 노드)에 도착할 때까지의 경우를 모두 구해야 하는 경우에 사용한다.
이처럼, dfs, bfs는 상호 보완적인 알고리즘이므로 둘 다 알고 있어야 한다.
시간복잡도는 인접 행렬의 경우 O(N^2), 인접 리스트의 경우 O(V + E)를 갖는다. 따라서, 노드의 갯수가 아주 많아질 경우 인접행렬을 사용해서 문제를 풀 수가 없다. 그러므로 인접 리스트를 통해서 위의 코드와 같은 기능을 갖도록 하는 코드를 본인이 직접 작성해보길 바란다.
이로써 그래프 순회 알고리즘인 BFS, DFS의 정의, 원리, 기본예제와 심화 예제 풀이, 활용을 알아보았다. 이 게시글에서 영감을 받아서 꼭 좋은 결과 있길 바란다. 하는일 다 잘풀리길 바랍니다~
그리고 아래에 프린트문 지운 코드 올린다.
import copy
# 반복적 DFS
def dfs_iterative(graph, input_start):
answer = []
start = input_start
stack = [start]
path = []
visited = [False] * len(graph)
for i in range(len(graph)):
for j in range(len(graph[i])):
if i == j:
graph[i][j] = 0
count = 0
while stack:
count += 1
start = stack.pop()
visited[start] = True
path.append(start)
cands = []
for i in range(len(graph[start])-1,-1, -1):
if not visited[i] and graph[start][i] == 1:
cands.append(i)
# 갈 수 있는 노드 있음
if cands:
stack.extend(cands)
else:
# 끝자락에 도착
answer.append(copy.deepcopy(path))
while True and path:
try:
temp = path[-1]
except:
return answer
arr = []
for i in range(len(graph[temp])-1, -1, -1):
if graph[temp][i] == 1 and not visited[i]:
arr.append(i)
if arr:
break
return answer
graph = [[1, 1, 1, 1, 0, 0, 0, 0],
[1, 1, 0, 0, 0, 0, 0, 0],
[1, 0, 1, 0, 0, 1, 0, 0],
[1, 0, 0, 1, 1, 0, 0, 1],
[0, 0, 0, 1, 1, 0, 0, 0],
[0, 0, 1, 0, 0, 1, 1, 0],
[0, 0, 0, 0, 0, 1, 1, 0],
[0, 0, 0, 1, 0, 0, 0, 1]]
start = 1
print("반복 DFS 정답: ", dfs_iterative(graph, start))
# 재귀적 DFS
def recurse(graph, start, answer, path, input_start):
path.append(start)
cands = []
# 갈 수 있는 노드 찾기
for i in range(len(graph[start])):
if i != start and graph[start][i] == 1:
cands.append(i)
# 갈 수 있는 노드가 없다면, 현재까지의 path를 answer의 원소로 저장하고, return하는 것으로 종료
if not cands:
answer.append(copy.deepcopy(path))
return
# 갈 수 있는 노드가 있다면, 그 노드로 가는 경로에 해당하는 graph의 원소를 0으로 바꾸고, 재귀 호출
else:
while cands:
cand = cands.pop(0)
graph[start][cand] = 0
graph[cand][start] = 0
recurse(graph, cand, answer, path, input_start)
# 반복이 끝났다는 것은 해당 노드에서 더이상 갈 수 있는 노드가 없다는 뜻. 따라서 path에서 pop한다.
def dfs_recursive(graph, input_start):
path = []
answer = []
start = input_start
recurse(graph, start, answer, path, input_start)
return answer
graph = [[0, 1, 1, 1, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 1, 0, 0],
[1, 0, 0, 0, 1, 0, 0, 1],
[0, 0, 0, 1, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 1, 0],
[0, 0, 0, 0, 0, 1, 0, 0],
[0, 0, 0, 1, 0, 0, 0, 0]]
start = 1
print("재귀 DFS 정답: ", dfs_recursive(graph, start))
'공부 > 알고리즘' 카테고리의 다른 글
| [알고리즘 자습]그래프(Graph) - 5. 최소 신장 트리 - 프림(Prim) 알고리즘, 파이썬 (2) | 2020.03.04 |
|---|---|
| [알고리즘 자습]그래프(Graph) - 3. 위상 정렬, 파이썬(Python3) (0) | 2020.03.04 |
| [알고리즘 자습]그래프(Graph) - 1. BFS(너비우선탐색)의 정의와 활용, 예제, 파이썬(Python3) (1) | 2020.03.04 |
| [알고리즘 자습]그래프(Graph) - 0. 자료 구조 (0) | 2020.02.28 |
| [프로그래머스 탐욕법]저울 - Python3 (0) | 2020.02.28 |
