DFS vs BFS 접근방법

1. DFS와 BFS 접근방법

DFS : 이동한 정점의 값을 가지고 계속 연산을 하는 경우(재귀적으로 호출되는경우)
BFS : 최단거리 문제
ex1) 지구 상에 존재하는 모든 친구 관계를 그래프로 표현한 후 Ash 와 Vanessa 사이에 존재하는 경로를 찾는 경우

DFS - 모든 친구 관계를 다 살펴봐야할지도 모름
BFS - Ash와 가까운 관계부터 탐색

for문을 돌면서 탐색해야하는 정점이면서 방문하지 않은 경우, break으로 빠져나오면
DFS

그렇지 않고 계속해서 정점을 탐색한다면
BFS

2. 예제를 통해 접근

DFS 풀이법

DFS의 경우 , 인접행렬, 인접리스트 , 스택 총 3가지 방법을 이용해 구현가능

1. 인접행렬 : 정점의 개수가 적은 경우에만 사용하는 것을 권장한다. 왜냐하면, 정점n개에 대해 행렬의 크기가 n*n만큼 차지하기 때문에 n의 수가 시간복잡도 O(n^2)가 된다.
2. 인접리스트 : 모든 정점을 탐색하는 최악의 경우를 제외한 나머지 경우 인접행렬보다는 빠른 시간복잡도인 O(n+E)이다. (E는 간선의 개수)
3. 스택 : 1,2번과 달리 재귀호출을 하지 않는 방식으로 구현가능하다.

음료수 얼려 먹기

1) 0의 값이 상하좌우로 연결되어 있는 노드를 모두 묶기 위해 DFS
2) 간선 하나로 갈 때의 경우 (깊게 하나만 간선으로 갈 경우) DFS

n, m = map(int, input().split())

graph = []
for i in range(n):
	graph.append(list(map(int, input())))
    
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
    
result = 0
for i in range(n):
	for j in range(m):
    	if dfs(i, j) == True:
        	result += 1
print(result)

BFS 풀이법

BFS는 큐를 이용하여 구현

미로 탈출

1) 시작 지점에서부터 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색함으로 BFS
2) 모든 간선의 비용이 동일할 때 - > BFS(너비 우선 탐색)

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 = x + dy[i]
        # 미로 찾기 공간을 벗어난 경우 무시
        if nx < 0 or ny < 0 or nx >= n or ny >= m:
        	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))