그래프 탐색 알고리즘 - DFS/BFS
스택
- 먼저 들어 온 데이터가 나중에 나가는 형식의 자료구조
- 입구와 출구가 동일한 형태로 시각화
- 예시: 박스 쌓기, 접시 쌓기
- 삽입, 삭제 두 연산으로 구성됨
- 삽입 : 맨 끝에 추가
- 삭제 : 맨 끝 원소 삭제
- 파이썬 - 단순 리스트를 사용하면 된다.
append()
: 리스트 오른쪽에 요소 추가
pop()
: 마지막 요소 삭제
- 출력 시 순서를 뒤집으면 최상단 원소부터 출력가능
큐
- 먼저 들어온 데이터가 먼저 나가는 형식의 자료구조
- 입구과 출구과 모두 뚫려있는 터널과 같은 형태로 시각화
- 예시 : 은행 대기열
- deque 라이브러리 사용
- 일반 리스트를 사용해도 구현 가능하지만, 시간복잡도가 더 높아짐
queue = deque()
객체 만들어 사용
append()
: 가장 오른쪽에 데이터 추가 O(1)
popleft()
: 가장 왼쪽 데이터 삭제 O(1)
- 나중에 들어온 원소부터 출력하려면 reverse 후 출력
재귀 함수
- 자기 자신을 호출하는 함수를 의미
- DFS를 구현할 때 자주 사용됨
- 재귀 함수를 문제 풀이에 사용할 때는 종료 조건을 반드시 명시해야 함
- 그렇지 않으면 함수가 무한히 호출될 수 있음
- 종료 조건을 포함한 재귀함수 예제
def recursion(i):
if i == 5:
return
print(i, '번째 재귀함수에서', i+1, '번째 재귀함수 호출')
recursion(i+1)
print(i, '번째 재귀함수 종료')
recursion(1)
실행결과1 번째 재귀함수에서 2 번째 재귀함수 호출
2 번째 재귀함수에서 3 번째 재귀함수 호출
3 번째 재귀함수에서 4 번째 재귀함수 호출
4 번째 재귀함수에서 5 번째 재귀함수 호출
4 번째 재귀함수 종료
3 번째 재귀함수 종료
2 번째 재귀함수 종료
1 번째 재귀함수 종료
- 팩토리얼 구현 예제
def factorial(n):
if n <= 1:
return 1
return n*factorial(n-1)
print(factorial(10))
- 유클리드 호제법 예제 : 두 자연수에 대한 최대공약수를 구하는 알고리즘
def gcd(a, b):
r = a % b
if r == 0:
return b
return gcd(b, r)
print(gcd(162, 192))
- 유의사항
- 복잡한 알고리즘을 간결하게 작성할 수 있다.
- 단 다른 사람이 이해하기 어려운 형태가 될 수 있으므로 신중하게 사용해야 한다
- 반복문으로 동일한 기능을 구현할 수 있고, 경우에 따라 반복문이 유리할 수도, 재귀함수가 유리할수도 있다.
- 컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓임 → 스택을 사용해야 할 때 스택 라이브러리 대신 재귀함수를 이용하는 경우가 많다!
- ex ) 재귀함수를 이용해 DFS를 구현하기도 한다
DFS (Depth-First Search)
- 깊이 우선 탐색. 깊은 부분을 우선적으로 탐색하는 알고리즘
- 스택 자료구조(혹은 재귀함수)를 이용.
- 탐색 시작 노드를 스택에 삽입하고 방문 처리
- 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄
- 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]
]
visited = [False] * 9
dfs(graph, 1, visited)
BFS - Breadth-First Search
- 너비 우선 탐색
- 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘
- 최단거리 구하기
- 큐 자료구조를 이용
- 탐색 시작 노드를 큐에 삽입하고 방문 처리
- 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리
- 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]
]
visited = [False] * 9
bfs(graph,1,visited)
문제 : 음료수 얼려 먹기
- 삽입 : 맨 끝에 추가
- 삭제 : 맨 끝 원소 삭제
append()
: 리스트 오른쪽에 요소 추가pop()
: 마지막 요소 삭제- 출력 시 순서를 뒤집으면 최상단 원소부터 출력가능
- 먼저 들어온 데이터가 먼저 나가는 형식의 자료구조
- 입구과 출구과 모두 뚫려있는 터널과 같은 형태로 시각화
- 예시 : 은행 대기열
- deque 라이브러리 사용
- 일반 리스트를 사용해도 구현 가능하지만, 시간복잡도가 더 높아짐
queue = deque()
객체 만들어 사용append()
: 가장 오른쪽에 데이터 추가 O(1)popleft()
: 가장 왼쪽 데이터 삭제 O(1)- 나중에 들어온 원소부터 출력하려면 reverse 후 출력
재귀 함수
- 자기 자신을 호출하는 함수를 의미
- DFS를 구현할 때 자주 사용됨
- 재귀 함수를 문제 풀이에 사용할 때는 종료 조건을 반드시 명시해야 함
- 그렇지 않으면 함수가 무한히 호출될 수 있음
- 종료 조건을 포함한 재귀함수 예제
def recursion(i):
if i == 5:
return
print(i, '번째 재귀함수에서', i+1, '번째 재귀함수 호출')
recursion(i+1)
print(i, '번째 재귀함수 종료')
recursion(1)
실행결과1 번째 재귀함수에서 2 번째 재귀함수 호출
2 번째 재귀함수에서 3 번째 재귀함수 호출
3 번째 재귀함수에서 4 번째 재귀함수 호출
4 번째 재귀함수에서 5 번째 재귀함수 호출
4 번째 재귀함수 종료
3 번째 재귀함수 종료
2 번째 재귀함수 종료
1 번째 재귀함수 종료
- 팩토리얼 구현 예제
def factorial(n):
if n <= 1:
return 1
return n*factorial(n-1)
print(factorial(10))
- 유클리드 호제법 예제 : 두 자연수에 대한 최대공약수를 구하는 알고리즘
def gcd(a, b):
r = a % b
if r == 0:
return b
return gcd(b, r)
print(gcd(162, 192))
- 유의사항
- 복잡한 알고리즘을 간결하게 작성할 수 있다.
- 단 다른 사람이 이해하기 어려운 형태가 될 수 있으므로 신중하게 사용해야 한다
- 반복문으로 동일한 기능을 구현할 수 있고, 경우에 따라 반복문이 유리할 수도, 재귀함수가 유리할수도 있다.
- 컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓임 → 스택을 사용해야 할 때 스택 라이브러리 대신 재귀함수를 이용하는 경우가 많다!
- ex ) 재귀함수를 이용해 DFS를 구현하기도 한다
DFS (Depth-First Search)
- 깊이 우선 탐색. 깊은 부분을 우선적으로 탐색하는 알고리즘
- 스택 자료구조(혹은 재귀함수)를 이용.
- 탐색 시작 노드를 스택에 삽입하고 방문 처리
- 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄
- 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]
]
visited = [False] * 9
dfs(graph, 1, visited)
BFS - Breadth-First Search
- 너비 우선 탐색
- 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘
- 최단거리 구하기
- 큐 자료구조를 이용
- 탐색 시작 노드를 큐에 삽입하고 방문 처리
- 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리
- 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]
]
visited = [False] * 9
bfs(graph,1,visited)
문제 : 음료수 얼려 먹기
def recursion(i):
if i == 5:
return
print(i, '번째 재귀함수에서', i+1, '번째 재귀함수 호출')
recursion(i+1)
print(i, '번째 재귀함수 종료')
recursion(1)
실행결과1 번째 재귀함수에서 2 번째 재귀함수 호출
2 번째 재귀함수에서 3 번째 재귀함수 호출
3 번째 재귀함수에서 4 번째 재귀함수 호출
4 번째 재귀함수에서 5 번째 재귀함수 호출
4 번째 재귀함수 종료
3 번째 재귀함수 종료
2 번째 재귀함수 종료
1 번째 재귀함수 종료
def factorial(n):
if n <= 1:
return 1
return n*factorial(n-1)
print(factorial(10))
def gcd(a, b):
r = a % b
if r == 0:
return b
return gcd(b, r)
print(gcd(162, 192))
- 복잡한 알고리즘을 간결하게 작성할 수 있다.
- 단 다른 사람이 이해하기 어려운 형태가 될 수 있으므로 신중하게 사용해야 한다
- 반복문으로 동일한 기능을 구현할 수 있고, 경우에 따라 반복문이 유리할 수도, 재귀함수가 유리할수도 있다.
- 컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓임 → 스택을 사용해야 할 때 스택 라이브러리 대신 재귀함수를 이용하는 경우가 많다!
- ex ) 재귀함수를 이용해 DFS를 구현하기도 한다
- 깊이 우선 탐색. 깊은 부분을 우선적으로 탐색하는 알고리즘
- 스택 자료구조(혹은 재귀함수)를 이용.
- 탐색 시작 노드를 스택에 삽입하고 방문 처리
- 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄
- 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]
]
visited = [False] * 9
dfs(graph, 1, visited)
BFS - Breadth-First Search
- 너비 우선 탐색
- 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘
- 최단거리 구하기
- 큐 자료구조를 이용
- 탐색 시작 노드를 큐에 삽입하고 방문 처리
- 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리
- 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]
]
visited = [False] * 9
bfs(graph,1,visited)
문제 : 음료수 얼려 먹기
- 탐색 시작 노드를 큐에 삽입하고 방문 처리
- 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리
- 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]
]
visited = [False] * 9
bfs(graph,1,visited)
풀이 아이디어
- 특정한 지점의 주변 상, 하, 좌, 우를 살펴본 뒤 주변 지점 중에서 값이 0인데 아직 방문하지 않은 지점이 있으면 해당 지점을 방문한다.
- 방문 지점에서 다시 상, 하, 좌, 우를 살피면서 방문하는 과정을 반복한다. → 연결된 모든 지점을 방문한다.
- 모든 노드에 대하여 1~2번의 과정을 반복한다.
def dfs(x, y):
if 0 <= x < n and 0 <= y < m:
print(graph)
if graph[x][y] == 0:
graph[x][y] = 1
# 범위를 벗어나거나, 이미 방문한 노드이거나, 칸막이 노드를 만나면 함수를 종료한다.
dfs(x-1, y)
dfs(x+1, y)
dfs(x, y-1)
dfs(x, y+1)
# 현재 위치에서 탐색을 완료했으므로 True를 리턴
return True
else:
print(False)
return False
n, m = map(int, input().split())
graph = [list(map(int, input())) for _ in range(n)]
ans = 0
for i in range(n):
for j in range(m):
print('here is', i, j)
if dfs(i, j) == True:
print('here!')
ans += 1
print(ans)
문제 : 미로 탈출
풀이 아이디어
- BFS는 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색
- 상하좌우로 연결된 모든 노드까지의 거리가 1로 동일
- 따라서 (1,1) 지점부터 BFS 수행하여 모든 노드의 최단거리 값을 기록한다.
def bfs(x, y):
queue = deque()
queue.append((x, y))
while queue:
x, y = queue.popleft()
for dx, dy in di:
nx = dx + x
ny = dy + y
print(nx, ny)
if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == 1:
graph[nx][ny] = graph[x][y] + 1
queue.append((nx, ny))
else:
continue
return graph[n-1][m-1] # 마지막에 도달했을 때 = 최종 거리
from collections import deque
n, m = map(int, input().split())
graph = [list(map(int, input())) for _ in range(n)]
di = [(-1, 0), (1, 0), (0, -1), (0, 1)]
print(bfs(0, 0))
def bfs(x, y):
queue = deque()
queue.append((x, y))
while queue:
x, y = queue.popleft()
for dx, dy in di:
nx = dx + x
ny = dy + y
print(nx, ny)
if nx < 0 or nx >= n or ny < 0 or ny >= m:
print('범위 이탈')
continue
if graph[nx][ny] == 0:
print('괴물!')
continue
if graph[nx][ny] == 1:
print(nx, ny)
graph[nx][ny] = graph[x][y] + 1
queue.append((nx, ny))
return graph[n-1][m-1] # 마지막에 도달했을 때 = 최종 거리
from collections import deque
n, m = map(int, input().split())
graph = [list(map(int, input())) for _ in range(n)]
di = [(-1, 0), (1, 0), (0, -1), (0, 1)]
print(bfs(0, 0))
Author And Source
이 문제에 관하여(그래프 탐색 알고리즘 - DFS/BFS), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@devheyrin/DFS-BFS저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)