[Algorithm] BFS(Breadth-First-Search), DFS(Depth-First-Search)

BFS와 DFS 둘다 완전 탐색 알고리즘이다.

1. BFS(Breadth - First -Search) : 너비우선탐색

https://www.codecademy.com/article/tree-traversal

Tree Traversal: Breadth-First Search vs Depth-First Search | Codecademy

 

• 시작 노드에서 인접 노드를 모두 방문하고 방문한 노드에서 인접 노드를 모두 방문하는 것을 반복하게 된다. 
• BFS를 이용하게 되면 가중치가 없다는 가정 하에 처음 방문한 노드들의 집합이 최단 경로가 없다.
• 최대한 넓게 이동한 다음 , 더 이상 갈 수 없을 떄 아래로 이동한다.
• 시간복잡도는 O(n)

from collections import deque				# 큐 자료구조를 생성하기 위한 deque import

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 visited[i] == False :
        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)

• BFS는 queue 자료구조를 사용해야 한다. → 노드를 방문하면서 인접한 노드 중 방문하지 않았던 노드의 정보만 큐에 넣어 먼저 큐에 들어있던 노드부터 방문하면 된다. 
• BFS는 탐색 시작 노드에서 목표노드까지 최단 거리를 구하는 문제에서 보통 사용한다. → 탐색 과정에서 최초로 목표 노드에 도달 했을 때가 최단 거리임이 보장되기 때문이다.

BFS의 다른 구현 코드 

def BFS(graph, start_node):
    # graph에서 BFS 된 list와 BFS 되야 할 list생성 
    visited = list()
    need_visited = list()

    #시작 노드 visited 리스트에 넣기
    need_visited.append(start_node)
    # need_ visited 리스트가 없을 때까지 반복 수행
    while need_visited:
        node = need_visited.pop(0)

        # visited에 node가 없을 때
        if node not in visited:
            #visited 리스트에 node  넣고,
            visited.append(node)
            # 해당 node에 연결된 노드 extand 사용해서  need_visited 리스트에 넣기
            need_visited.extend(graph[node])
    print(visited)


graph = dict()

graph['A'] = ['B','C']
graph['B'] = ['A','D']
graph['C'] = ['A','G','H','I']
graph['D'] = ['B','E','F']
graph['E'] = ['D']
graph['F'] = ['D']
graph['G'] = ['C']
graph['H'] = ['C']
graph['I'] = ['C','J']
graph['J'] = ['I']

BFS(graph, 'A')


------------------------------------------------------------------------------------------



from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    
    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.add(node)
            print(node, end=' ')  # 방문한 노드 출력
            queue.extend(graph[node] - visited)

# 예제 그래프
graph = {
    1: {2, 3, 4},
    2: {1, 5, 6},
    3: {1},
    4: {1},
    5: {2},
    6: {2}
}

bfs(graph, 1)

ex) baekjoon - 2178 

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

from collections import deque
N, M = map(int,input().split())
arr = [list(map(int,input())) for _ in range(N)]

dx = [0,1,0,-1]
dy = [1,0,-1,0]

def bfs(x,y) :
  queue = deque()
  queue.append((x,y))

  while queue :
    x,y = queue.popleft()
	
    for i in range(4) :					# 현재 위치에서 4가지 방향으로 위치 확인
      nx = x + dx[i]
      ny = y + dy[i]

      if nx < 0 or nx >= N or ny < 0 or ny >= M :		# 위치가 벗어나면 안되는 조건 
        continue

      if arr[nx][ny] == 0 :								# 벽이면 무시
        continue

      if arr[nx][ny] == 1 :								# 카운트 값을 더한다.	
        arr[nx][ny] = arr[x][y] + 1
        queue.append((nx , ny))

  return arr[N-1][M-1]									# 마지막 값에서 카운트 값을 뽑는다. 

print(bfs(0,0))

 

 

경로 탐색 문제에서 가장 중요한 것
1. dx = [0,1,0,-1] dy[1,0,-1,0] 잡고 가기
2. if x < 0 or x >= N or y < 0 or y >= N : continue 경로 조건 추가

 

2. DFS(Depth - First -Search) : 깊이우선탐색

https://www.codecademy.com/article/tree-traversal

Tree Traversal: Breadth-First Search vs Depth-First Search | Codecademy

• root node 에서 시작해서 다음 분기로 넘어가기 전애 해당 분기를 완벽하게 탐색하는 방법을 의미한다. 
• DFS는 기본적으로 Stack 자료구조를 활용하고 자기자신을 호출하는 순환 알고리즘(재귀)의 형태를 가지고 있다. 
• 시간복잡도는 O(n)이다
•  Python은 재귀 호출 횟수가 1000회로 제한되어있어 그 이상 쓰려면 sys 모듈의 setrecursionlimit()으로 제한을 늘려야 할 때도 있다.

import sys
sys.setresursionlimit(10**6)

def dfs(graph,v,visited):
    visited[v] = True							# v 노드 방문
    print(v,end=" ")							# 방문 노드 출력
    for i in graph[v]:
    	if visited[i] == False :				# 방문하지 않은 노드가 있다면 않았다면
        	dfs(graph,i,visited)			
            
graph = [
	[],											# 0 번 노드는 null
    [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번 노드부터 방문하자

*Another DFS

#dfs는 stack 구조를 활용한다, 오른쪽 부터 깊이 우선 탐색
def DFS(graph, start_node):
    #visted 리스트와 need_visited 리스트 생성
    visited = list()
    need_visited = list()
    #출발 node need_visited 리스트에 삽입
    need_visited.append(start_node)

    #need_visited node가 없을 때 까지 반복
    while need_visited :
        node = need_visited.pop()

        if node not in visited :
            
            visited.append(node)
            need_visited.extend(graph[node])

    print(visited)


graph = dict()

graph['A'] = ['B','C']
graph['B'] = ['A','D']
graph['C'] = ['A','G','H','I']
graph['D'] = ['B','E','F']
graph['E'] = ['D']
graph['F'] = ['D']
graph['G'] = ['C']
graph['H'] = ['C']
graph['I'] = ['C','J']
graph['J'] = ['I']

DFS(graph, 'A')

 

ex) baekjoon - 1743

https://www.acmicpc.net/problem/1743

1743번: 음식물 피하기

import sys
sys.setrecursionlimit(10**6)
N,M,K = map(int,input().split())
board = [['.'] * (M) for _ in range(N)]
visited = [[False] * M for _ in range(N)]

dy = (0,1,0,-1) 
dx = (1,0,-1,0)

for _ in range(K) :
  r,c = map(int,input().split())
  board[r-1][c-1] = '#'

def is_valid_coord(y,x) :
  return 0 <= y < N and 0 <= x < M

sz = 0
ans = 0
def dfs(y,x) :
  global ans,sz

  visited[y][x] = True
  sz += 1
  ans = max(ans,sz)

  for k in range(4) :
    ny = y + dy[k]
    nx = x + dx[k]
    if is_valid_coord(ny,nx) and visited[ny][nx] == False and board[ny][nx] == '#' :
      dfs(ny,nx)

for i in range(N) :
  for j in range(M) :
    if visited[i][j] == False and board[i][j] == '#' :
      sz = 0
      dfs(i,j)

print(ans)

chat GPT 에서 DFS와 BFS를 검색해보았다...

DFS (Depth-First Search)와 BFS (Breadth-First Search)는 그래프 탐색 알고리즘으로, 각각 다음과 같은 특징을 가지고 있습니다.

DFS로 풀어야 하는 문제 유형:

1. 그래프의 모든 경로를 탐색해야 할 때.
2. 그래프에서 사이클을 찾아야 할 때.
3. 그래프에서 연결 요소(Connected Component)를 찾아야 할 때.
4. 깊이 우선 탐색 순서가 중요한 문제, 예를 들어 전위 순회(pre-order traversal), 후위 순회(post-order traversal) 등.

BFS로 풀어야 하는 문제 유형:

1. 그래프에서 최단 경로를 찾아야 할 때.
2. 그래프에서 노드 간의 최소 거리를 계산해야 할 때.
3. 그래프에서 두 노드 간의 최소 이동 횟수를 구해야 할 때.
4. 그래프에서 너비 우선 탐색 순서가 중요한 문제, 예를 들어 최소 이동 횟수 등.

DFS는 스택(Stack) 또는 재귀 함수를 사용하여 구현할 수 있으며, 현재 경로에서 더 이상 진행할 수 없을 때까지 깊이 우선으로 탐색합니다. 반면에 BFS는 큐(Queue)를 사용하여 구현하며, 현재 경로에서 다음 노드들을 순차적으로 탐색합니다.

따라서, 위에 제시한 문제 유형에 따라 DFS 또는 BFS를 선택하여 적절한 그래프 탐색 알고리즘을 적용할 수 있습니다.

라고 한다...정리해보자면 ,

 

	DFS	BFS
동작 원리	stack	queue
구현 방법	재귀 함수 이용	큐 자료구조 사용

 

BFS는 from collections import deque 자료구조 사용하고 최단거리문제를 풀때 사용한다
DFS는 재귀함수(recursion) 사용하고 모든 경우의 수를 확인해야 할 때 사용한다.

참고 : 이것이 취업을 위한 코딩 테스트다 with 파이썬 )

https://github.com/ndb796/python-for-coding-test

GitHub - ndb796/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체