코테 BFS

그래프 탐색 종류

• BFS : Breadth-first search (너비 우선 탐색) : 자기 자식을 우선 탐색
• DFS : Depth-first search (깊이 우선 탐색) : 자식의 자식을 먼저 탐색

 queue)= BFS

stack = DFS

 

아이디어

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

queue는 파이프 같이 생각 자료구조, 들어온 순서대로 나가게 됨 -> 123123

stack 은 한쪽이 막힌 파이트 같은 자료고조, 들어온 곳으로 나가게 됨 -> 123321

 

시간 복잡도

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

BFS : O( vertex +Edge)

 

라이브코딩

• 아이디어 >
• 2중 for -> 값 1 && 방문 X -> BFS
• BFS 돌면서 그림 개수 +1,  최대값을 갱신류
• BFS : Breadth-first search (너비 우선 탐색) : 자기 자식을 우선 탐색
• DFS : Depth-first search (깊이 우선 탐색) : 자식의 자식을 먼저 탐색
•  queue)= BFS

stack = DFS

 

 

 

아이디어

 

시작점에 연결된 vertex 찾기

찾은 vertex를 queue에 저장

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

queue는 파이프 같이 생각 자료구조, 들어온 순서대로 나가게 됨 -> 123123

 

stack 은 한쪽이 막힌 파이트 같은 자료고조, 들어온 곳으로 나가게 됨 -> 123321

 

 

 

시간 복잡도

 

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

 

BFS : O( vertex +Edge)

 

 

 

라이브코딩

 

아이디어 >

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

BFS 돌면서 그림 개수 +1, 최대값을 갱신

• 시간복잡도
  • BFS : O(V+E) = V + 4V = 5V = 5 * M * N (M, N = 500 -> 문제에서 n(1<_ n <_ 500) ) 
  • V : M * N = 500 * 500
  • E : V * 4 = 4 * 500 * 500
  • V + E : 5 * 250000 = 100만 < 2억 ->> 가능!
• 자료구조
  • 그래프 전체 지도 : int[][]
  • 방문 여부 : bool[][]
  • Queue( BFS )

 

백준 1926번

import sys import = 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 bts(y, x):     rs = 1     q = [(y, x)]     while q:         ey, ex = q.pop()         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, nx))     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:         ch[j][i] = True         # 전체 그림 갯수를 +1         cnt += 1         # BFS > 그림 크기를 구해주고         # 최대값 갱신         maxv = max(maxv, bfs(j,i)) print(cnt) print(maxv)