BFS (Breadth-first search) 알고리즘

00 개요

• 목표: 코딩테스트 뽀개기!

1. 그래프 탐색이란

• 어떤 것들이 연속해서 이어질 때, 모두 확인하는 방법
• Graph: Vertex (어떤 것) + Edge (이어지는 것)

2. 그래프 탐색 종류

• BFS: Breadth-first search (너비 우선 탐색)
• DFS: Depth-first search (깊이 우선 탐색)

 

01 BFS

1. BFS란

• Breadth-first search, 너비 우선 탐색
• 그래프 탐색 종류 중 하나
• Queue 사용, Stack 미사용!

2. 준비하기

1) 아이디어

• 시작점에 연결된 Vertex 찾기 
• 찾은 Vertex를 Queue에 저장 
• Queue의 가장 먼저 것 뽑아서 반복

2) 시간 복잡도

• O(V+E)

3) 자료구조

• 검색할 그래프 방문
• 여부 확인(재방문 금지) 
• Queue: BFS 실행

3. 연습 문제: 백준 1926

• 링크: https://www.acmicpc.net/problem/1926

1) 문제

• Q:
  • 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로로 연결된 것은 연결이 된 것이고 대각선으로 연결이 된 것은 떨어진 그림이다. 그림의 넓이란 그림에 포함된 1의 개수이다.
• 입력:
  • 첫째 줄에 도화지의 세로 크기 n(1 ≤ n ≤ 500)과 가로 크기 m(1 ≤ m ≤ 500)이 차례로 주어진다. 두 번째 줄부터 n+1 줄 까지 그림의 정보가 주어진다. (단 그림의 정보는 0과 1이 공백을 두고 주어지며, 0은 색칠이 안된 부분, 1은 색칠이 된 부분을 의미한다)
• 출력:
  • 첫째 줄에는 그림의 개수, 둘째 줄에는 그 중 가장 넓은 그림의 넓이를 출력하여라. 단, 그림이 하나도 없는 경우에는 가장 넓은 그림의 넓이는 0이다.
• 예제 입력 1:

6 5 1 1 0 1 1 0 1 1 0 0 0 0 0 0 0 1 0 1 1 1 0 0 1 1 1 0 0 1 1 1

• 예제 출력 1

4 9

 

2) 사전 계획 수립

• 아이디어
  • 2중 for문, 값 1 && 반문 X => BFS로 진행 결정
  • BFS를 통해 그림 개수 + 1, 최대값 갱
• 시간 복잡도
  • BFS: O(V+E)
    • V = m * n
    • E = V * 4 (각 노드 당 방향이 4개이기에 - 상 우 하 좌)
  • O(V+E) = V + E = V + 4V = 5(m*n)
    • m, n 최대값 = 500, 500
    • => O(V+E) = 5(500*500) = 100만 < 2억 => 가능 (주의: 다른 분은 500만번을 Max로 권장) 
• 자료 구조
  • 그래프 전체 지도: int[ ][ ] → str[ ][ ]
  • 방문 여부: bool [ ][ ]
  • Queue(BFS)

3) 실습

# input을 요구하는 경우
import sys
input = sys.stdin.readline
# n, m = map(int, input().split())
# mapped_list = [list(map(int, input().split())) for _ in range(n)]

n, m = 6, 5
data = '''
1 1 0 1 1
0 1 1 0 0
0 0 0 0 0
1 0 1 1 1
0 0 1 1 1
0 0 1 1 1
'''
mapped_list = [a.replace(' ', '') for a in data.strip().split('\n')]        # ['11011', '01100', '00000', '10111', '00111', '00111']
chk = [[False] * m for _ in range(n)]
count = 0
maxSize = 0
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]

def bfs(y, x):
    size = 1
    queue_bfs = [(y, x)]
    while queue_bfs:
        ey, ex = queue_bfs.pop()
        for k in range(4):
            ny = ey + dy[k]
            nx = ex + dx[k]
            if 0 <= ny < n and 0 <= nx < m:
                if mapped_list[ny][nx] == '1' and chk[ny][nx] == False:
                    chk[ny][nx] = True
                    size += 1
                    queue_bfs.append((ny, nx))
    return size
    
for j in range(n):
    for i in range(m):
        if mapped_list[j][i] == '1' and chk[j][i] == False:
            chk[j][i] = True
            count += 1
            maxSize = max(maxSize, bfs(j, i))
print(f'%d\n%d' % (count, maxSize))

• 반환값:

 

 

참조

1. 개발자 장고, https://www.youtube.com/watch?v=ansd5B27uJM&list=PLi-xJrVzQaxXC2Aausv_6mlOZZ2g2J6YB&index=2
2.  
3.