[CS] BFS - 너비 우선 탐색(최단거리)

1. 그래프 탐색 : 어떤것(Vertex)들이 연속해서 이어질때(Edge), 모두 확인하는 방법

 

2. BFS vs DFS

- BFS: 자식을 먼저 봄

- DFS: 자식의 자식을 먼저 봄

 

3. BFS 아이디어

- 시작점에 연결된 vertex 찾기

- 찾은 vertex를 queue에 저장 (들어온 순서대로 나감) => 넓게 퍼지며 탐색

- queue의 가장 먼저 것을 뽑아서 반복

- 최단거리에 BFS 쓰는 이유? BFS는 가까운 노드부터(거리1짜리 다음 거리2짜리,,,) 차례차례 탐색하기 때문에 처음 도착한 순간이 곧 최단거리가 된다.

# 큐에 들어오는 순서

[1,2,5,3,4,6]
1 => 2랑 5 추가 => 1 제거
2 => 2랑 열된 3 => 2제거
5 => 5랑 연결된 4 => 5제거
3 => 4는 이미 있으니까 넘어감 => 3제거
4 => 6이 연결되어 있으니까 6추가

 

4. BFS 시간복잡도

- 시간복잡도: 알고리즘이 얼마나 오래 걸리는지

- BFS : O(V+E)

# 시간복잡도
1,a,b,2,5,d,3,f,4,e,g,6

 

5. BFS 자료구조

- 검색할 그래프

- 방문여부 확인(재방문 금지)

- Queue: BFS 실행

 

6. 연습문제

- 백준: https://www.acmicpc.net/problem/1926

 

1) 아이디어

- 2중 for => 값이 1 & 방문 X => BFS

- BFS 돌면서 그림 갯수 +1, 최댓값을 갱신

 

2) 시간복잡도

- BFS: O(V+E)

- 문제에서 m과 n은 최대 500

- V => m*n => 500*500

- E => 최대 4개 연결, 넉넉잡아 4V => 4*500*500

- O => 5V => 5*500*500 => 약 100만 < 1초에 약 2억개인데 2억개 미만이니까 가능!

 

3) 자료구조

- 그래프 전체 지도 => 1과 0으로 이루어져 있으니까 2차원 배열 생성: int[ ][ ] 

- 방문: bool [ ] [ ] 

- Queue(BFS)

 

4) 입력 빠르게 받기

import sys
input = sys.stdin.readline

 

5) 문제 풀이

from collections import deque

n,m = map(int, input().split())
map = [ list(map(int, input().split())) for _ in range(n)]
chk = [[False]*m for _ in range(n)]

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

def bfs(y,x):
	rs = 1 # 그림의 넓이
	q = deque()
    q.append((y,x))
    chk[y][x] = True  # 방문처리 여기서 해줘야 중복방문 안 생김
    
    while q:
    	ey, ex = q.popleft() # 다시 사라짐
        for k in range(4): # → ↓ ← ↑ 순으로 순회
        	ny = ey + dy[k]
            nx = ex + dx[k]
            if 0 <=ny<n and 0 <=nx<m: # 그림 크기에 초과하거나 이미 방문하면 넘어가기
            	if map[ny][nx] == 1 and chk[ny][nx] ==False:
                	rs += 1
                    chk[ny][nx] = True
                    q.append((ny,nex)) # 방문안한거 있으면 추가
	return rs 
    
cnt = 0
maxv = 0
for j in range(n):
	for i in range(m):
    	if map[j][i] == 1 and chk[j][i]==False:
        	# 방문하면 True로 변경해줌
            chk[j][i] == True
        	# 전체 그림 갯수를 +1
            cnt += 1
            # BFS > 그림 크기를구해주고 결과를 최댓값에 갱신 
            maxv = max(maxv, bfs(j,i)) # map이 1일때만 bfs(크기세기)

print(cnt)
print(maxv)

 

※ 참고 자료: 개발자 장고 https://youtu.be/ansd5B27uJM?si=rN9iI3q_bjOBb5KG