4강. 알고리즘 - DFS/BFS

예시 그래프

<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)
# 1 2 7 6 8 3 4 5

 

예시 문제: 음료수 얼려먹기

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)

<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)
# 1 2 3 8 7 4 5 6

 

예시 문제: 미로 탈출

from collections import deque
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]

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]

print(bfs(0,0))