[백준,PS,BFS][PYTHON] #1012 . 유기농배추

from collections import deque

def bfs(a,b,m,n):
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]
    global count
    count = count +1 #bfs를 할때마다 map에서 순서를 구분해주기 위해서
    maps[a][b] = count
    while q:        
        for _ in range(len(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:
                    if visited[nx][ny] == 0 and maps[nx][ny] == 1 :
                        q.append([nx,ny])
                        maps[nx][ny]   = count #bfs횟수를 map에 넣어준다.
                        visited[nx][ny] = 1#방문함으로 바꿔준다.
            
        


test_case = int(input())


for _ in range(test_case):
    count =0
    m,n,num = map(int, input().split())
    maps = [[0] * m for _ in range(n)]
    visited = [[0] * m for _ in range(n)]
    
    q = deque()
    
    for i in range(num):
        y,x = map(int,input().split())
        maps[x][y] =1
        
    for a in range(n):
        for b in range(m):
            if maps[a][b] == 1 and visited[a][b] ==0:#map의 다음갈곳이 1이면서 방문하지않았던곳을 큐에넣어줘야함
                q.append([a,b])#큐에 집어넣고
                visited[a][b] = 1#방문함으로 바꿔주고
                bfs(a,b,m,n)#bfs실시함
    
    result = max(map(max,maps)) # 2차원 리스트에서 최대값을 구하는 방법
    print(result)

#실행결과부분
#for i in range(len(maps)):
#    print(maps[i] , sep = " \n")
#print("@@@@@@@@@@@@@@@@")                
#for i in range(len(visited)):
#    print(visited[i] , sep = " \n")