[알고리즘] BFS (너비 우선 탐색)

강의 출처 : 나동빈님 유튜브 강의

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

• BFS는 너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘
• BRS는 큐 자료구조를 이용하며, 구체적 동작 과정은 다음과 같음
  • 탐색 시작 노드를 큐에 삽입하고 방문처리
  • 큐에서 노드를 꺼낸 후, 해당 노드에 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하여 방문처리
  • 더 이상 2번의 과정을 수행할 수 없을 때 까지 반복

---

1-1. BFS 동작 예시

• [Step 0] 그래프를 준비 (방문기준 : 번호가 낮은 인접노드부터) / 시작노드 : 1
  

---

• [Step 1] 시작노드 ‘1’을 큐에 삽입하고 방문처리
  

---

• [Step 2] 큐에서 노드 ‘1’을 꺼내 방문하지 않은 인접노드 ‘2’, ‘3’, ‘8’을 큐에 삽입하여 방문 처리
  

---

• [Step 3] 큐에서 노드 ‘2’을 꺼내 방문하지 않은 인접노드 ‘7’ 을 큐에 삽입하여 방문 처리
  

---

• [Step 4] 큐에서 노드 ‘3’을 꺼내 방문하지 않은 인접노드 ‘4’, ‘5’ 을 큐에 삽입하여 방문 처리
  

---

• [Step 5] 큐에서 노드 ‘8’을 꺼내고 방문하지 않은 인접노드가 없으므로 무시
  

---

• 이러한 과정을 반복하여 전체 노드의 탐색 순서(큐에 들어간 순서)는 다음과 같음
• 탐색 순서 : 1 → 2 → leftpop(1) → 3 → 8 → 2(leftpop) → 7 → 3(leftpop) → 4 → 5 → 8(leftpop) → 6
  

---

1-2. BFS 소스코드 예제

# 각 노드가 연결된 정보를 표현 (2차원 리스트)
graph =[
		#0 [],
		#1 [2,3,8],
		#2 [1,7],
		#3 [1,4,5],
		#4 [3,5],
		#5 [3,4],
		#6 [7],
		#7 [2,6,8],
		#8 [1,7]
]

# 각 노드가 방문된 정보를 표현(1차원 리스트)
visited = [False] * 9
# False = 한 번도 인접하지 않는 것으로 초기화

# 정의된 DFS 함수 호출
bfs(graph, 1, visited)

---

from collections import deque

# BFS 메서드 정의
def bfs(graph, start, visited):
	# 큐 구현을 위해 deque 라이브러리 사용
	queue = deque([start])  
	**# 현재 노드 방문처리**
	visited[start] = True
	
	# 큐가 빌 때까지 반복
	while queue:
		# 큐에서 원소를 뽑아 출력
		v = queue.popleft()
		print(v, end=' ')
		# 아직 방문하지 않은 인접 원소들을 큐에 삽입
		for i in graph[v]: # v = 인덱스
			if not visited[i]:
				queue.append(i)
				visited[i] = True

>>> 1 2 3 8 7 4 5 6

---

2. 문제풀이 : 미로탈출

동빈이는 NxM 크기의 직사각형 형태의 미로에 갇혔다. 미로에는 여러 괴물이 있어 이를 피해 탈출해야 한다. 동빈이의 위치는 (1,1)이며 미로의 출구는 (N,M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다. 이 때 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시 돼 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 이 때 동빈이가 탈출하기 위해 움직여야하는 최소 칸의 개수를 구하라. 칸을 셀 때, 시작 칸과 마지막 칸 모두 포함해서 계산한다.

💡 문제 해결 아이디어
1. BFS는 시작시점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색
2. 상, 하, 좌, 우로 연결된 모든 노드로의 거리가 1로 동일
3. 따라서 (1,1) 지점부터 BFS를 수행해 모든 노드의 최단거리 값을 기록하면 해결 가능
4. 예시로 다음과 같이 3x3 크기의 미로가 있다고 가정

---

• 최단 경로의 값들이 1씩 증가하는 형태로 변형
  

💡 Cording

from collections import deque
# 그래프 크기 입력
n, m = map(int, input().split()) # 3 3
-------------------------------------------------------------------------------
# 그래프 입력
#110
#010
#011
gragh=[]
for i in range(n):
  gragh.append(list(map(int, input())))
------------------------------------------------------------------------------- 
# 이동좌표 설정
dx = [-1, 1, 0, 0] # 좌우 이동
dy = [0, 0, -1, 1] # 상하 이동
-------------------------------------------------------------------------------
# bfs 함수 정의
def bfs(x, y):
  queue = deque() 
  queue.append((x, y)) # append (0,0)
-------------------------------------------------------------------------------
  while queue : #0이되기 전까지
    x, y = queue.popleft() # x= 0, y=0

    for i in range(4):
      nx = x + dx[i] # 좌우 이동한 결과 # 0-1, 0+1, 0+0, 0+0
      ny = y + dy[i] # 상하 이동한 결과 # 0+0, 0+0, 0-1, 0+1
-------------------------------------------------------------------------------
      if nx < 0 or nx >= n or ny < 0 or ny >= m: # 그래프 범위를 벗어나도 continue
        continue       
      if gragh[nx][ny] == 0: # 이동한 좌표가 0이어도 continue
        continue
-------------------------------------------------------------------------------       
      if gragh[nx][ny] == 1: # 이동한 좌표가 1이면,
        gragh[nx][ny] = gragh[x][y] + 1 # 이동한 좌표 = 이동 전 좌표 + 1 #1 → 20
        queue.append((nx, ny)) # 이동한 위치를 append (1,0)
-------------------------------------------------------------------------------
  # queue가 0이되면 현재 각각 좌표에 -1
  # 마지막지점(탈출구) 값을 반환
  # input : 3 by 3 → 2 by 2 = 5
  return gragh[n - 1][m - 1]
-------------------------------------------------------------------------------  
#시작좌표
print(bfs(0,0))