★BFS&DFS Upper-Intermediate I - 16 Solved★

☝️ 중상급의 BFS/DFS 유형은 그래프 연결 요소 / 연결 요소 내의 노드 개수 / 최단 거리(Easy) 3개의 알고리즘으로 분류할 수 있다.

---

★ 11724 연결 요소의 개수 ★

☝️ DFS

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10000)
N,M=map(int,input().split())

#dfs
def dfs(graph,start,visited):
    visited[start] = True

    for node in graph[start]:
        if not visited[node]:
            dfs(graph,node,visited)


#graph
graph=[[] for _ in range(N+1)]

for _ in range(M):
    u,v=map(int,input().split())
    graph[u].append(v)
    graph[v].append(u)

#visited
visited=[False]*(N+1)

ans=0

for node_num in range(1,N+1):
    if visited[node_num] == False:
        dfs(graph,node_num,visited)
        ans+=1
print(ans)

 

☝️ BFS

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

N,M=map(int,input().split())

def bfs(graph,start,visited):
    queue = deque([start])
    visited[start] = True

    while queue:
        node = queue.popleft()
        
        for i in graph[node]:
            if not visited[i]:
                queue.append(i)
                visited[i]=True
        

#graph
graph=[[] for _ in range(N+1)]

for _ in range(M):
    u,v=map(int,input().split())
    graph[u].append(v)
    graph[v].append(u)

#visited
visited=[False]*(N+1)

num_of_connected_components = 0

for node in range(1,N+1):
    if visited[node] == False:
        bfs(graph,node,visited)
        num_of_connected_components+=1

print(num_of_connected_components)

 

☝️ 그래프의 정보가 주어진 상태에서, 서로 연결된 node 묶음의 개수 - 즉 연결 요소 (connected components)의 개수를 묻는 문제

 

☝️ 연결요소의 개수를 찾기 위해서는,

① 각 node별로(1부터 시작)

② visited 유무가 False라면, dfs / bfs graph searching을 진행해 연결 node들을 모두 visited True로 해줌

③ 한 번의 searching으로 한 개의 묶음이 생기며 계속 counting

④ 이후 False인 시작 node를 또 찾아 계속 dfs/bfs 진행

⑤ update하며 add up되는 변수 최종 연결요소의 개수를 print

 

★ 핵심: 모든 node for문으로 돌려 not visited라면 dfs / bfs searching 진행하고, 연결요소 개수 += 1 ★

 

☝️ 즉! 그래프 연결요소의 개수 찾기는 visited=False의 모든 node를 시작 node로 dfs/bfs 진행하며 counting add up!

---

★ 1012 유기농 배추 ★

 

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10000)

def dfs(l,i,j):

    if l[i][j] == 1:
        l[i][j]=0
        
        if (i-1)>=0: dfs(l,i-1,j)
        if (i+1)<=(M-1): dfs(l,i+1,j)
        if (j-1)>=0: dfs(l,i,j-1)
        if (j+1)<=(N-1): dfs(l,i,j+1)
        
        return True


for _ in range(int(input())):
    caterpillars=0
    M,N,K=map(int,input().split())

    #area
    area=[[0]*N for _ in range(M)]

    for _ in range(K):
        X,Y=map(int,input().split())

        area[X][Y] = 1
    
    for i in range(M):
        for j in range(N):
            if area[i][j] == 1:
                dfs(area,i,j)
                caterpillars+=1
    print(caterpillars)

 

☝️ 그래프 이론의 전형적인 연결요소 개수 구하기

 

☝️ 각 그래프를 돌면서 1이면, dfs를 시행해 상/하/좌/우 1인지 recursive하게 확인. 1이면 모두 0으로 바꾸고, 모든 dfs가 끝났다는 건 한 개의 묶음 형성 마무리 → 묶음 개수 counting 1 추가

 

☝️ dfs에서 항상 요소가 1일 때부터 시작하므로 모든 recursion이 마무리 되면 마지막에 최종적으로 True로 함수 끝냄 (리턴만 하면 됨)

---

★ 4963 섬의 개수 ★

 

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)

def dfs(graph,i,j):
    if graph[i][j]==1:
        graph[i][j]=0

        if (i-1)>=0:
            dfs(graph,i-1,j)

        if (i+1)<=(h-1):
            dfs(graph,i+1,j)
        
        if (j-1)>=0:
            dfs(graph,i,j-1)
        
        if (j+1)<=(w-1):
            dfs(graph,i,j+1)
        
        if (i-1)>=0 and (j-1)>=0:
            dfs(graph,i-1,j-1)
        
        if (i-1)>=0 and (j+1)<=(w-1):
            dfs(graph,i-1,j+1)
        
        if (i+1)<=(h-1) and (j-1)>=0:
            dfs(graph,i+1,j-1)
        
        if (i+1)<=(h-1) and (j+1)<=(w-1):
            dfs(graph,i+1,j+1)
    
    return True

while 1:
    w,h=map(int,input().split())

    if (w,h) == (0,0): break

    #graph
    graph=[]
    for _ in range(h):
        graph.append(list(map(int,input().split())))

    n=0
    for i in range(h):
        for j in range(w):
            if graph[i][j] == 1:
                dfs(graph,i,j)
                n+=1
    print(n)

 

☝️ 다만, 대각선 4개의 방향으로 이동할 수 있다는 조건만 추가됨. 4개의 if문만 추가하면 끝

---

★ 2667 단지번호붙이기 ★

 

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

def bfs(graph,start_x,start_y,n,queue):
    queue.append((start_x,start_y))

    while queue:
        v = queue.popleft()

        x,y=v[0],v[1]

        if 0<=(x-1):
            if graph[x-1][y] == 1:
                queue.append((x-1,y))
                graph[x-1][y]=0
                n+=1
        
        if (x+1)<=(N-1):
            if graph[x+1][y]==1:
                queue.append((x+1,y))
                graph[x+1][y]=0
                n+=1
        
        if 0<=(y-1):
            if graph[x][y-1]==1:
                queue.append((x,y-1))
                graph[x][y-1]=0
                n+=1
        
        if (y+1)<=(N-1):
            if graph[x][y+1]==1:
                queue.append((x,y+1))
                graph[x][y+1]=0
                n+=1

    return n
    

N=int(input())
num_of_towns=0
num_of_towns_list=[]

#graph
graph=[]
for _ in range(N):
    graph.append(list(map(int,input().rstrip())))

for i in range(N):
    for j in range(N):
        if graph[i][j]==1:
            graph[i][j]=0
            num_of_towns+=1
            num_of_houses=1
            queue=deque()
            num_of_towns_list.append(bfs(graph,i,j,num_of_houses,queue))

print(num_of_towns)
print(*sorted(num_of_towns_list),sep='\n')

 

☝️ 연결요소의 개수 + 연결요소 내의 노드 개수를 묻는 문제 유형

 

☝️ 즉, 연결요소 개수를 묻는 전형적인 문제 유형에서, 추가로 각 연결요소 내에 노드가 몇 개 인지까지 묻는 문제

 

☝️ 이번에는 BFS로 풀었다.

① 매 번 연결요소 묶음을 찾을 때마다, queue 초기화, 묶음 개수 변수 1 증가, 찾은 부분 0으로 설정, 노드 개수 변수 0 설정

② BFS함수 내에서는 먼저 start queue에 넣고

 

→ while queue문

(1) queue에서 popleft()로 제일 먼저 queue에 넣은 node 추출.

 

(2) 총 네 방향별로 노드값이 1인지 확인, 1인지 확인하면 visited 되었음

→ queue에 넣음

→ 해당 graph값 0 설정

→ 노드 개수 변수 1 증가

---

★ 1926 그림 ★

 

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

def BFS(paper, n, m, visited, start):
  area=1
  queue = deque([start])
  visited[start[0]][start[1]] = True
  dx,dy=[1,-1,0,0],[0,0,1,-1]
  while queue:
    v=queue.popleft()
    for i in range(4):
      nx,ny=v[0]+dx[i],v[1]+dy[i]
      if 0<=nx<n and 0<=ny<m:
        if not visited[nx][ny] and paper[nx][ny]==1:
          visited[nx][ny]=True
          area+=1
          queue.append((nx,ny))
  return area

n,m=map(int,input().split())
paper=[]
visited=[[0]*m for _ in range(n)]
for _ in range(n):
  paper.append(list(map(int,input().split())))
areas=[]
num_area=0
for i in range(n):
  for j in range(m):
    if paper[i][j]==1 and not visited[i][j]:
      areas.append(BFS(paper,n,m,visited,(i,j)))
      num_area+=1

if num_area==0:
  print(0,0,sep='\n')
else:
  print(num_area,max(areas),sep='\n')

 

☝️ 위 2667 연결요소 개수 + 연결요소 넓이 유형과 동일

---

★ 2468 안전 영역 ★

 

import sys, copy
input = sys.stdin.readline
sys.setrecursionlimit(10000)

N=int(input())
graph=[]
ans=1

def dfs(graph, i, j, N, limit):
    if (i-1)>=0 and not visited[i-1][j] and graph[i-1][j] > limit:
        visited[i-1][j] = True
        dfs(graph,i-1,j,N,limit)
    
    if (i+1)<N and not visited[i+1][j] and graph[i+1][j] > limit:
        visited[i+1][j] = True
        dfs(graph,i+1,j,N,limit) 
    
    if (j-1)>=0 and not visited[i][j-1] and graph[i][j-1] > limit:
        visited[i][j-1] = True
        dfs(graph,i,j-1,N,limit)
    
    if (j+1)<N and not visited[i][j+1] and graph[i][j+1] > limit:
        visited[i][j+1] = True
        dfs(graph,i,j+1,N,limit)
    
    return True

for _ in range(N):
    l=list(map(int,input().split()))
    graph.append(l)

max_h = max(map(max,graph))

for limit in range(max_h):
    visited=[[0]*N for _ in range(N)]
    n=0
    for i in range(N):
        for j in range(N):
            if not visited[i][j] and graph[i][j] > limit:
                    dfs(graph,i,j,N,limit)
                    n+=1
    ans=max(ans,n)

print(ans)

 

 

☝️ 전형적인 연결요소 개수 문제

 

+ 2차원 그래프에서 최대,최소는 max(map(max,graph))인 map함수로 한번에 구하기 가능

 

+ dfs로 풀었지만 양방향으로 진행하는 연결요소 개수 구하기는 bfs 추천

---

★ 2583 영역 구하기 ★

 

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

def BFS(graph, N, M, v, visited, square):
    dx=[0,0,1,-1]
    dy=[1,-1,0,0]
    
    queue=deque([v])
    visited[v[0]][v[1]] = True

    while queue:
        nv = queue.popleft()
        for i in range(4):
            nx=nv[0]+dx[i]
            ny=nv[1]+dy[i]

            if nx>=0 and nx<M and ny>=0 and ny<N:
                if graph[nx][ny]!='!' and not visited[nx][ny]:
                    visited[nx][ny] = True
                    queue.append((nx,ny))
                    square+=1
    return square


M,N,K=map(int,input().split())
area_cnt,area=0,[]

#forming a graph
graph=[[0]*N for _ in range(M)]
for _ in range(K):
    x1,y1,x2,y2=map(int,input().split())
    for x in range(M-1-(y2-1),M-1-(y1)+1):
        for y in range(x1,x2):
            graph[x][y]='!'

visited=[[0]*N for _ in range(M)]
for x in range(M):
    for y in range(N):
        if not visited[x][y] and graph[x][y] != '!':
            area_cnt+=1
            square=1
            area.append(BFS(graph, N, M, (x,y), visited, square))
        

print(area_cnt)
print(*sorted(area))

 

☝️ 직사각형의 두 좌표로 주어진 그래프 !로 채우기(이 때, 문제에서의 (x,y)와 그래프에서의 (x,y)가 달라 가로/세로 규칙 찾고 이에 맞게 배치

 

☝️ BFS에서 상하좌우 양방향 dx, dy 벡터 만들고 for _ in range(4)문 돌려 nx와 ny 만든 다음 nx와 ny 범위에 있는 지 확인이 여러 if문 작성보다 더 간결.

 

☝️ area의 개수는 연결요소의 개수: for문 조건에 맞으면 +=1 / area 넓이는 연결요소마다 기존 1에서 넓힐때마다, 즉 queue에 들어갈 요소가 생길 때마다 +=1

---

★ 14940 쉬운 최단거리 ★

 

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

def BFS(area, n, m, visited, start, depths):
  queue = deque([start])
  visited[start[0]][start[1]] = True
  depths[start[0]][start[1]] = 0 #goal
  
  dx,dy=[1,-1,0,0],[0,0,1,-1]
  while queue:
    v=queue.popleft()
    for i in range(4):
      nx,ny=v[0]+dx[i],v[1]+dy[i]
      if 0<=nx<n and 0<=ny<m:
        if not visited[nx][ny]:
          visited[nx][ny]=True
          if area[nx][ny]!=0:
            depths[nx][ny] = depths[v[0]][v[1]]+1
            queue.append((nx,ny))
  return area

n,m=map(int,input().split())
area,ans=[],[]
gx,gy=0,0

visited=[[0]*m for _ in range(n)]
depths=[[-1]*m for _ in range(n)]
row_ind=0
for _ in range(n):
  
  l = list(map(int,input().split()))
  for i in range(len(l)):
    if l[i] == 2:
      gx,gy=row_ind,i
    elif l[i] == 0:
      depths[row_ind][i] = 0

  area.append(l)
  row_ind+=1


BFS(area, n, m, visited, (gx,gy), depths)

for i in depths:
  print(*i)

 

☝️ 목표지점에서 BFS 시작해 모든 node의 최단경로, 즉 depth 구하는 전형적인 최단거리 유형

 

☝️ + 다만 도달이 원래 안되는 0 지점은 0 지점: graph 만들면서 마킹

/ 도달 가능하나 도달 못하는 지점인 -1은 -1로 초기화한 depth에서 시작

---

★ 1743 음식물 피하기 ★

 

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

N,M,K=map(int,input().split())
graph=[['.']*M for _ in range(N)]
visited=[[False]*M for _ in range(N)]
cur_max=0

def BFS(graph, visited, i, j, area):
  queue = deque([(i,j)])
  visited[i][j] = True

  dx,dy=[0,0,1,-1],[1,-1,0,0]
  
  while queue:
    v = queue.popleft()
    for k in range(4):
      nx,ny=v[0]+dx[k],v[1]+dy[k]
      if 0<=nx<N and 0<=ny<M:
        if not visited[nx][ny] and graph[nx][ny] == '#':
          area+=1
          queue.append((nx,ny))
          visited[nx][ny] = True

  return area


for _ in range(K):
  r,c=map(int,input().split())
  graph[r-1][c-1]='#'

for i in range(N):
  for j in range(M):
    if graph[i][j] == '#' and not visited[i][j]:
      area=1
      cur_max=max(cur_max,BFS(graph, visited, i, j, area))

print(cur_max)

 

☝️ #에 해당하는 음식물, 즉 연결 노드 영역 넓이 구하기 유형

---

★ 1303 전쟁 - 전투 ★

 

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

N,M=map(int,input().split())
visited=[[False]*N for _ in range(M)]
graph=[[] for _ in range(M)]
me,you=0,0

def BFS(graph, visited, start, color, area):
    queue=deque([start])
    visited[start[0]][start[1]] = True
    dx,dy=[-1,1,0,0],[0,0,-1,1]
    while queue:
        x,y=queue.popleft()
        for i in range(4):
            nx,ny=x+dx[i],y+dy[i]
            if 0<=nx<M and 0<=ny<N:
                if not visited[nx][ny]:
                    if graph[nx][ny] == color:
                        area+=1
                        visited[nx][ny]=True
                        queue.append((nx,ny))
    return area
for i in range(M):
    line=list(input().rstrip())
    graph[i] = line

#me
for i in range(M):
    for j in range(N):
        if graph[i][j] == 'W':
            if not visited[i][j]:
                area=1
                area=BFS(graph,visited,(i,j),'W',area)
                me+=(area*area)
        else: #'B'
            if not visited[i][j]:
                area=1
                area=BFS(graph,visited,(i,j),'B',area)
                you+=(area*area)

print(me,you)

 

☝️ W와 B 각각의 연결노드 넓이 구하는 유형. 이 때 단 1개의 함수 BFS만 효율적으로 사용. W와 B 각각 traversing하므로 visited에서 겹칠 일 없으므로 visited도 한 번만 사용

---

★ 3184 양 ★

 

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

R,C=map(int,input().split())
graph=[]
visited=[[False]*C for _ in range(R)]

def bfs(graph, visited, start, l, w):
    x,y=start[0],start[1]
    visited[x][y] = True
    queue=deque([start])
    dx,dy=[0,0,-1,1],[-1,1,0,0]
    if graph[x][y] == 'o': l+=1
    elif graph[x][y] == 'v': w+=1
    while queue:
        v = queue.popleft()
        for i in range(4):
            nx,ny=v[0]+dx[i],v[1]+dy[i]
            if 0<=nx<R and 0<=ny<C:
                if not visited[nx][ny] and graph[nx][ny]!='#':
                    visited[nx][ny]=True
                    queue.append((nx,ny))
                    if graph[nx][ny] == 'o':
                        l+=1
                    elif graph[nx][ny] == 'v':
                        w+=1
    return (l,w)





for _ in range(R):
    graph.append(list(input().rstrip()))

lamb,wolf=0,0


for i in range(R):
    for j in range(C):
        if not visited[i][j] and graph[i][j] != '#':
            l,w=0,0
            lw = bfs(graph, visited, (i,j), l, w)
            if lw[0] > lw[1]:
                lamb+=lw[0]
            else:
                wolf+=lw[1]

print(lamb, wolf)

 

☝️ 각 연결 영역별로 양과 늑대의 수를 각각 카운트하고 양과 늑대의 대소관계에 때라 lamb, wolf 최종 변수값 출력

---

★ 1325 효율적인 해킹 ★

 

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

def bfs(graph, visited, start):
    visited[start] = True
    queue=deque([start])
    ans=0
    while queue:
        v = queue.popleft()
        for nv in graph[v]:
            if not visited[nv]:
                ans+=1
                visited[nv]=True
                queue.append(nv)
    return ans

N,M=map(int,input().split())
graph=[[]for _ in range(N+1)]
for _ in range(M):
    A,B=map(int,input().split())
    graph[B].append(A)
hackable_nums=[0]
for start in range(1,N+1):
    visited=[False]*(N+1)
    hackable_nums.append(bfs(graph, visited, start))
ans_num=max(hackable_nums)
for x in range(len(hackable_nums)):
    if hackable_nums[x] == ans_num:
        print(x,end=' ')

 

☝️ A가 B를 신뢰한다는 건, graph[B]에 A를 연결할 수 있다는 뜻이고 graph[A]에 B 연결은 아니다. (양방향이 아님에 주의)

 

☝️ BFS로 방문하는 node 개수 카운트

---

★ 17086 아기 상어 2 ★

 

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

N,M=map(int,input().split())
graph,dist=[],[[-1]*M for _ in range(N)]
dx,dy=[0,0,-1,1,1,1,-1,-1],[-1,1,0,0,1,-1,-1,1]

def BFS(node):
    queue=deque([node])
    while queue:
        v=queue.popleft()
        x,y,d=v[0],v[1],v[2]
        for i in range(8):
            nx,ny=x+dx[i],y+dy[i]
            if 0<=nx<N and 0<=ny<M:
                if (d+1)<dist[nx][ny] or dist[nx][ny] == -1:
                    dist[nx][ny] = (d+1)
                    queue.append((nx,ny,d+1))

for x in range(N):
    l=list(map(int,input().split()))
    graph.append(l)

for x in range(N):
    for y in range(M):
        if graph[x][y] == 1:
            dist[x][y] = 0
            BFS((x,y,0))

print(max(max(x) for x in dist))

 

☝️ 각 상어별로 자기 자신은 거리가 0으로 설정, 8방향 뻗어나가면서 dist 거리 depth로 1씩 증가.

 

★ 이 때 상어별로 visited 배열 선언하면 메모리 초과. update되는 dist를 기준으로 queue에 (x,y,d) append 여부 결정. 일단 첫 상어일 경우 dist값이 -1일 때 모두 append / 이미 update된 dist라면, d+1(현재 상어 기준 거리)이 기존 dist[nx][ny]보다 작을 경우만 queue에 append. 작지 않다면 앞으로 더 진행해도 이미 거리는 점점 +1씩 증가하면서 탐색할 필요가 없기에(최단거리 구하므로) append 필요 없음.

: 위 예시를 보면 첫번째 상어(2행)를 출발점으로 dist update 이후 두번째 상어(3행)을 출발점으로 dist update하려고 할 때, 위, 오른쪽 위, 오른쪽 방향의 숫자가 현재 두번째 상어 dist + 1 보다 작거나 같다. 즉, 이후 아무리 진행하려고 해도 의미가 없다는 뜻(어차피 더 커지거나 같기만 할 뿐. 최솟값을 구하려는 문제의 의도가 아니다)

 

★ visited[] 배열 사용 없이, update되는 dist로 node를 queue의 append 할 지의 여부를 판단할 수 있다는 점 기억하기

---

★ 16174 점프왕 젤리 (Large) ★

 

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

N=int(input())
graph,visited=[],[[False]*N for _ in range(N)]
for _ in range(N):
    graph.append(list(map(int,input().split())))
dq=deque([(0,0)])
while dq:
    node = dq.popleft()
    x,y=node[0],node[1]
    visited[x][y]=True
    #right nx,ny
    rnx,rny=x,y+graph[x][y]
    if (rnx,rny) == (N-1,N-1):
        print('HaruHaru')
        sys.exit()
    if 0<=rny<N and not visited[rnx][rny]:
        visited[rnx][rny] = True
        if graph[rnx][rny] != 0:
            dq.append((rnx,rny))
    
    #down nx,ny
    dnx,dny=x+graph[x][y],y
    if (dnx,dny) == (N-1,N-1):
        print('HaruHaru')
        sys.exit()
    if 0<=dnx<N and not visited[dnx][dny]:
        visited[dnx][dny] = True
        if graph[dnx][dny] != 0:
            dq.append((dnx,dny))    
print('Hing')

 

☝️ 오른쪽/아래로만 이동 가능하지만, 한 번 방문한 곳은 이후 경로가 똑같으므로 방문 처리 / 이 때, graph 값이 0으로 적힌 경우 더 이상 진행할 필요 없으므로 방문처리하고 append()에 넣지 x

---

★ 11123 양 한마리... 양 두마리... ★

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

def BFS(graph, visited, start):
    queue=deque([start])
    visited[start[0]][start[1]]=True
    dx,dy=[-1,1,0,0],[0,0,-1,1]
    while queue:
        v = queue.popleft()
        for i in range(4):
            nx,ny=v[0]+dx[i],v[1]+dy[i]
            if 0<=nx<H and 0<=ny<W:
                if not visited[nx][ny] and graph[nx][ny] == '#':
                    visited[nx][ny] = True
                    queue.append((nx,ny))


T=int(input())
for _ in range(T):
    H,W=map(int,input().split())
    grid=[]
    visited=[[False]*W for _ in range(H)]
    for _ in range(H):
        grid.append(list(input().rstrip()))
    sheeps=0
    for i in range(H):
        for j in range(W):
            if not visited[i][j] and grid[i][j] == '#':
                sheeps+=1
                BFS(grid,visited,(i,j))
    print(sheeps)

---

★ 5958 Space Exploration ★

 

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

def BFS(graph,start):
    visited[start[0]][start[1]] = True
    queue=deque([start])
    dx,dy=[-1,1,0,0],[0,0,-1,1]
    while queue:
        v=queue.popleft()
        x,y=v[0],v[1]
        for i in range(4):
            nx,ny=x+dx[i],y+dy[i]
            if 0<=nx<N and 0<=ny<N:
                if not visited[nx][ny] and graph[nx][ny] == '*':
                    queue.append((nx,ny))
                    visited[nx][ny] = True


N=int(input())
graph=[]
for _ in range(N):
    graph.append(list(input().rstrip()))
visited=[[False]*N for _ in range(N)]
ans=0
for i in range(N):
    for j in range(N):
        if not visited[i][j] and graph[i][j] == '*':
            BFS(graph,(i,j))
            ans+=1
print(ans)

---