백준 1012번 유기농 배추

2667번과 유사한 문제로 구하는 값이 다르다 여기서는 묶을의 개수만 구하면 된다

문제를 풀때 좌표를 잘 생각해서 풀어야한다 x,y의 그래프가 x축 기준으로 반전이어서 인덱스를 잘 설정하지 않으면 인덱스 오류가 나오기 쉬운 문제이다

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


def bfs(line,x,y,n,m):
    line[x][y] = 0
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]
    q = deque()
    cnt = 1
    q.append([x,y])
    while q :
        a,b = q.popleft()
        for i in range(4):
            x1 = a + dx[i]
            y1 = b + dy[i]
            if x1 < 0 or x1 >=n or y1 < 0 or y1 >=m:
                continue

            if line[x1][y1] == 1:
                line[x1][y1] = 0
                q.append([x1,y1])
                cnt += 1
    return cnt


#인접한 노드중에서 1인 것을 묶어서 묶인개수를 구해라
t = int(input()) #테스트 케이스

for _ in range(t):
    count = []
    m,n,k = map(int,input().split())
    line = [[0 for _ in range(m)] for _ in range(n)] #배추가 심어질 밭
    
    for i in range(k):
        y,x = map(int,input().split())
        line[x][y] = 1
    
    
    for i in range(m):
        for j in range(n):
            if line[j][i] == 1:
                count.append(bfs(line,j,i,n,m))
            
    print(len(count))