(알고리즘)BFS(Breadth-First-Search) 너비 우선 탐색 - 파이썬 + 백준 2178 풀이

---

BFS

---

1. BFS동작 예시

- 가까운 노드부터 우선적으로 탐색하는 알고리즘

- BFS는 큐를 사용하여 너비 우선으로 탐색한다.

집어 넣은 순서대로 1 -> 2 -> 3 -> 5 -> 4 -> 8 -> 6 -> 7

---

2. BFS 코드 예시

from collections import deque 
#queue를 사용하기 위해 쓰임 리스트를 사용해도 되지만,
#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]: #만약 v=1일때 i는 차레대로 2,3,8이 됨.
      if not visited[i]:
        queue.append(i)
        visited[i] = True

graph=[
  [],
  [2, 3, 5],
  [1, 4, 8],
  [1, 6, 7],
  [2, 8],
  [1, 8],
  [3, 7],
  [3, 6],
  [2, 5]
]

visited = [False]*len(graph)
bfs(graph, 1, visited)

#출력
# 1 2 3 5 4 8 6 7 

 

---

3. BFS 예제문제 1

문제풀러가기

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

2178번: 미로 탐색

---

문제

---

풀이

1.  x=N-1, y=M-1이 도착 위치이다.

2. 상하좌우로 이동하며 1씩 증가하여 계산하면 된다. 

---

코드

import queue
import sys
from collections import deque
N,M = map(int, sys.stdin.readline().split())
arr=[]
xy = [[-1,0],[1,0],[0,-1],[0,1]] #상하좌우로 움직이기 위한 리스트
max_arr = [[0]*M for _ in range(N)] #거리 계산용 리스트
visited = [[False]*M for _ in range(N)] # 방문 한 노드 거르기 위한 리스트
queue=deque()

# arr리스트 만들기
for i in range(N):
  a = str(sys.stdin.readline().strip())
  b=[]
  for i in range(len(a)):
    b.append(int(a[i]))
  arr.append(b)

def bfs(x,y):
  queue.append((x,y)) # 정점 노드 넣어주기
  visited[x][y]=True  # 방문 표시 하기
  max_arr[x][y]=1 # 처음 출발 거리도 포함하므로 1부터 시작

  while queue:
    x,y = queue.popleft()
    
    if x==N and y==M:
      break

    for i in range(len(xy)):
      nx = x + xy[i][0]
      ny = y + xy[i][1]
      if nx>=0 and nx<N and ny>=0 and ny<M:
        if(arr[nx][ny]==1 and not visited[nx][ny]==True):
          visited[nx][ny]=True
          queue.append((nx,ny))
          max_arr[nx][ny] = max_arr[x][y]+1

  print(max_arr[N-1][M-1]) # 큐에 요소가 없어 while문이 끝나면 출력

bfs(0,0)    

 

코드풀이

위 코드가 이해가 안되면 아래 코드를 복사하여 돌려보시면,

출력결과와 코드를 대조하면서 보시면 코드가 어떻게 돌아가는지 보일 겁니다.

import queue
import sys
from collections import deque
N,M = map(int, sys.stdin.readline().split())
arr=[]
xy = [[-1,0],[1,0],[0,-1],[0,1]] #상하좌우
max_arr = [[0]*M for _ in range(N)]
visited = [[False]*M for _ in range(N)]
queue=deque()

# arr리스트 만들기
for i in range(N):
  a = str(sys.stdin.readline().strip())
  b=[]
  for i in range(len(a)):
    b.append(int(a[i]))
  arr.append(b)

print("arr:",arr)
def bfs(x,y):
  queue.append((x,y))
  print("queue:",queue)
  visited[x][y]=True
  max_arr[x][y]=1

  print("visited:",visited)
  print("max_arr:",max_arr)

  while queue:
    x,y = queue.popleft()
    print("x:",x,"y:",y)

    if x==N and y==M:
      break

    for i in range(len(xy)):
      nx = x + xy[i][0]
      ny = y + xy[i][1]
      print("nx:",nx,"ny:",ny)
      if nx>=0 and nx<N and ny>=0 and ny<M:
        if(arr[nx][ny]==1 and not visited[nx][ny]==True):
          visited[nx][ny]=True
          queue.append((nx,ny))
          max_arr[nx][ny] = max_arr[x][y]+1
          print("visited:",visited)
          print("max_arr",max_arr)
          print("queue:",queue)
  print(max_arr[N-1][M-1])

bfs(0,0)    

 

도움이 되셨다면 왼쪽 하단 하트 눌러주세요:)

감사합니다~!