1. DFS
개념: 깊이 우선 탐색으로 깊은 부분을 우선적으로 탐색하는 알고리즘이다.
구현: 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)
2. BFS
개념: 너비 우선 탐색이며 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘이다.
구현: BFS는 큐 자료구조를 사용한다.
동작:
- 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
- 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리한다.
- 더 이상 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)
3. 예제
- 예제1) 음료수 얼려먹기: 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 문제
아이디어:
1) 특정한 지점의 상, 하, 좌, 우를 살펴본 뒤에 주변 지점 중에서 값이 '0'이면서 아직 방문하지 않은 지점이 있다면 해당 지점을 방문
2) 방문한 지점에서 다시 상, 하, 좌, 우를 살펴보며서 방문을 진행하는 과정을 반복하면, 연결된 모든 지점을 방문
3) 모든 노드에 대하여 1~2번 과정을 반복하여 방문하지 않은 지점의 수를 카운트
def dfs(x, y):
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)
- 예제2) 미로 탈출: 괴물을 피해 탈출하는 최소 칸의 개수를 구해라
아이디어:
1) BFS를 이용해서 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색한다.
2) 상, 하, 좌, 우로 연결된 모든 노드로의 거리가 1로 동일하여 모든 노드의 최단 거리 값을 기록하면 해결할 수 있다.
from collections import deque
def bfs(x, y):
queue =deque()
queue.append((x, y))
while queue:
x, y = queue.popleft()
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())
graph = []
for i in range(n):
graph.append(list(map(int, input())))
dx =[-1,1,0,0]
dy =[0,0,-1,1]
print(bfs(0,0))
