🚶‍♂️Road to 코테(8) - BFS

본 게시물은 BaaarkingDog님의 실전 알고리즘 강의를 통해 공부한 것을 정리합니다.

[추가] 용감하게 시작하는 코딩테스트

[추가] 코딩 테스트 합격자 되기 - 파이썬

[추가] 좌충우돌, 파이썬으로 자료구조 구현하기

BFS

다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘
그래프 자료구조에서 모든 노드를 방문하기 위해 만든 알고리즘이다.

정점(노드)와 간선(엣지)로 구성된 자료구조 이다.

좌표를 방문하면 표시를 남기고 큐에 넣는다. 큐가 빌 때까지 큐의 front를 빼고 좌표의 상하좌우를 살펴보며 큐에 넣어주는 작업을 반복한다.

(0,0)에서 상하좌우의 파란색 칸을 확인하여 (0,1)과 (1,0)을 큐에 넣는다.
(0,1)을 큐에서 pop해 상하좌우를 확인하면 (0,2)만 파란색이며 방문하지 않았으니 방문 표시를 남기고 큐에 넣는다.

이런 식으로 큐의 front를 pop시키며 방문 표시를 한다.

예시 구현을 해보자

from collections import deque
import sys

N, M = map(int, sys.stdin.readline().split())
mat = [
  [0, 1, 1, 1, 1, 1],
  [0, 1, 0, 0, 0, 1],
  [0, 1, 0, 1, 0, 1],
  [0, 1, 0, 1, 0, 0],
  [0, 0, 0, 1, 1, 0],
  [1, 1, 1, 1, 1, 0]
  ]
# for _ in range(N):
#     row = list(map(int, input().split()))
#     mat.append(row)
print(mat)

def bfs(y,x): # 좌표의 행과 열을 x,y를 반대로 넣어야한다. 
  visited=[[False]*M for _ in range(N)]
  dx=[-1,0,0,1] #열
  dy=[0,1,-1,0] #행
  
  visited[y][x]=True
  queue=deque()
  queue.append([y,x])
  while queue:
    loc=queue.popleft()
    print(loc[0],loc[1])
    for i in range(4):
      ny=loc[0]+dy[i]  #행 좌표 계산
      nx=loc[1]+dx[i]  #열 좌표 계산
      if (ny <0) or (ny>=N) or (nx<0) or( nx>=M):
        continue
      if mat[ny][nx]==1:
        continue
      if not visited[ny][nx]:
        visited[ny][nx]=True
        queue.append([ny,nx])
        
bfs(0,0)

BFS 단순 정리

1. 시작하는 칸을 큐에 넣고 방문했다는 표시 남김
2. 큐에서 원소 꺼내 상하좌우 칸에 대해 확인
3. 이미 방문한 칸이면 continue, 처음 방문하면 방문 표시 남기고 큐에 삽입
4. 큐가 빌 때까지 2번을 반복
   모든 칸이 큐에 1번씩 들어가므로 시간복잡도는 칸이 N개일 때(매트릭스 기준) O(n)개이다.

백준 문제 1926 : 색칠하기(Flood Fill)

from collections import deque
import sys

n,m=map(int,sys.stdin.readline().split())

pic=[]
for _ in range(n):
  row=list(map(int,sys.stdin.readline().split()))
  pic.append(row)

visited=[[False]*m for _ in range(n)]


def bfs(visited,y,x):
  temp=0
  dx=[-1,0,0,1] #열 좌상하우
  dy=[0,1,-1,0] #행 좌상하우
  
  visited[y][x]=True
  que=deque()
  que.append([y,x])
  while que:
    value=que.popleft()
    temp+=1
    for i in range(4):
      ny=dy[i]+value[0]
      nx=dx[i]+value[1]
      if nx<0 or nx>=m or ny<0 or ny>=n: #좌표가 벗어나면
        continue
      if pic[ny][nx]==0:
        continue
      if not visited[ny][nx]: #방문안한 그림을 방문하면
        visited[ny][nx]=True #해당 그림을 방문으로 바꾸고
        que.append([ny,nx]) # 큐에 넣는다. 
    
  return temp
        
res=[]
for i in range (n):
  for j in range(m):
    if pic[i][j]==1 and visited[i][j]==False: #그림이며 방문한적이 없을 때 bfs 시작
      res.append(bfs(visited,i,j))


print(len(res))
if len(res)==0:
  print(0)
else:
  print(max(res))

연습문제 백준 2178: 미로 탐색 / 응용 : 거리 측정

from collections import deque
import sys

n,m=map(int,sys.stdin.readline().split())

path=[]
for _ in range(n):
  row=list(map(int,input()))
  path.append(row)


dist=[[0]*m for _ in range(n)]

def dfs(dist,y,x):
  dx=[-1,0,0,1]
  dy=[0,-1,1,0]
  que=deque()
  que.append([y,x])
  
  dist[y][x]=1
  while que:
    next=que.popleft()
    for i in range(4):
      ny=dy[i]+next[0]
      nx=dx[i]+next[1]
      if nx<0 or ny<0 or ny>=n or nx>=m:
        continue
      if path[ny][nx]==0:
        continue
      if dist[ny][nx]==0: #아직 방문안한, 거리가 0으로 표시된 지점을 방문
        que.append([ny,nx]) # 큐에 좌표 넣고
        dist[ny][nx]=dist[next[0]][next[1]]+1 #거리를 하나씩 올리기
    
dfs(dist,0,0)
print(dist[n-1][m-1])      

BFS로 풀수 있는 문제는 모두 비슷해 보인다.

연습문제 3 백준 7576번 토마토

익은 토마토가 여러개면 시간이 얼마나 걸릴 것인가?
시작점이 여러 개인 BFS를 동시에 돌 수 있어야한다.
-> 여러 시작 점을 동시에 큐에 넣고 BFS를 돌려버리면 된다.

from collections import deque
import sys

n,m=map(int,sys.stdin.readline().split())

tomato=[]
for _ in range(m):
  row=list(map(int,sys.stdin.readline().split()))
  tomato.append(row)


day=[[0]*n for _ in range(m)]

que=deque()
for i in range(m):
  for j in range(n):
    if tomato[i][j]==0:
      day[i][j]=-1
    elif tomato[i][j]==1:	# 익은 토마토를 모두 que에 넣고 시작한다. 
      que.append([i,j])
      
while que:
  dx=[-1,0,0,1]
  dy=[0,1,-1,0]
  value=que.popleft()
  for i in range(4):
    ny=value[0]+dy[i]
    nx=value[1]+dx[i]
    if nx<0 or ny<0 or ny>=m or nx>=n:
      continue
    if day[ny][nx]>=0:
      continue
    day[ny][nx]=day[value[0]][value[1]]+1
    que.append([ny,nx])
    
ans=0      
for i in range(m):
  for j in range(n):
    ans=max(ans,day[i][j])

for i in range(m):
  for j in range(n):
    if day[i][j]== -1:  
      ans=-1
          

print(ans)