[백준] 1926번 - 그림 (BFS 기초)

참고: https://youtu.be/ansd5B27uJM

BFS 기초

그래프(Graph)?

: Vertex(어떤것) + Edge(이어지는것)

 

BFS

: Breadth-firest search (너비 우선 탐색)

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

BFS 알고리즘 해결 방법

1. 시간복잡도 구하기 O(V+E)
2. 검색할 그래프 확인하기
3. 방문여부 확인하기(재방문 금지)
4. Queue에 담아 BFS 실행

백준 1926번 - 그림

import sys
from collections import deque
input = sys.stdin.readline

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))
  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:
          chk[ny][nx] = True
          rs += 1 
          q.append((ny, nx))
  return rs

count = 0
maxNum = 0
for i in range(n):
  for j in range(m):
    if map[i][j] == 1 and chk[i][j] == False:
      chk[i][j] = True
      count += 1
      maxNum = max(maxNum, bfs(i, j))

print(count)
print(maxNum)

 

1) 아이디어

• 2중 for문 ⇒ 값이 1 && 방문 X ⇒ BFS
• BFS를 돌면서 그림 개수 +1, 최댓값 갱신

2) 시간복잡도

• BFS: O(V+E)
• V: 500 * 500
• E: 4V ⇒ 4 * 500 * 500
• V+E: 5 * 250000 = 100만 < 2억 >> 가능

3) 자료구조

• 그래프 전체 지도: int[][]
• 방문: bool[][]
• Queue(BFS)

 

노션(Notion) 정리

: https://fast-receipt-fe1.notion.site/BFS-2e09a51509344b858d85daa5f86b88b3

BFS

 

화이팅 💪