그래프 탐색 (1) BFS : 자식들부터 먼저 탐색

1. 그래프 탐색 : 어떤것들이 이어져있을 때 특정한 조건이 만족하는지 모두 탐색하는 방법

1-1. 그래프 : 어떤것들(Vertex) + 이어져있을때(Edge)

1-2. 탐색하는 방법

    1) BFS : 시작점에서 연결된 자식들부터 먼저 탐색, queue 자료구조를 사용

    2) DFS : 시작점에서 연걸된 자식의 자식들부터 깊게 파면서 검색, stack 자료구조를 사용

 

1) BFS

1. 방법 : 시작점에서 연결된 Vertex를 queue에 넣고 꺼내가면서, Edge를 따라가며 조건에 해당하는지 확인

2. 시간복잡도 : O(V+E)

3. 필요한 자료구조 

- 검색할 그래프

- 방문여부

- BFS를 실행할 queue

 

import sys
input=sys.stdin.readline()
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 dfs(y, x):
	rs = 1
    q = deque((y,x))
	while q:
    	ey, ex = q.popleft()
        for i in range(4):
        	ny = ey + dy[i]
            nx = ex + dx[i]
    		if 0 <=ny < n and 0 <=nx < m :
            	if map[ny][nx]==1 and chk[ny][nx]==False :
                	rs+=1
                    chk[ny][nx]=False
                    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] == Fasle:
        	chk[j][i] == True
            cnt+=1
            maxv=max(maxv, dfs(j, i))
            
print(cnt)
print(maxv)

 

참고

https://www.youtube.com/watch?v=ansd5B27uJM&t=863s