[Python]DFS와BFS 백준 1012

 문제

 https://www.acmicpc.net/problem/1012

앞의 문제와 다르지않다.

앞전에는 DFS를 활용하였으므로 이번엔 BFS를 통해 구현해보자.

import sys
from collections import deque
T=int(sys.stdin.readline())
 
def whiteworm(row,colume,matrix,N,M):
    q=deque()
    q.append([row,colume])#시작위치 넣어주고 시작
    matrix[row][colume]=2
    dx=[1,-1,0,0]
    dy=[0,0,1,-1]
    while q:
        [x,y]=q.popleft()#큐에 있는거 빼서 저장
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if 0<=nx<N and 0<=ny<M and matrix[nx][ny]==1:#해당 배추 근처에 배추가 있다면
                matrix[nx][ny]=2##체크
                q.append([nx,ny])#모두 큐에 넣어준다.
 
 
for _ in range(T):
    M,N,K=map(int,sys.stdin.readline().split())#가로길이/// 세로길이/// 배추가 심어져있는 위치 개수
    matrix=[[0 for _ in range(M)] for _ in range(N)]
    for _ in range(K):
        x,y=map(int,sys.stdin.readline().split())#열 행 순으로 받음
        matrix[y][x]=1
 
    count=0
    for i in range(N):
        for j in range(M):
            if matrix[i][j]==1:
                whiteworm(i,j,matrix,N,M)#연결된 모든 배추를 탐색후
                count+=1#그곳에 벌레를 넣어준다.
 
    print(count)