https://www.acmicpc.net/submit/1012/90022364

• 연결만 되어 있으면, 배추로 이동가능
• 군집 개수 물어보는 문제
• DFS로 해결 가능

• 배추의 좌표를 리스트로 구성
• dfs 함수 구현
  • 정점의 상하좌우가 리스트에 포함되어 있으면, 방문
  • 아닐 경우, dfs 함수 종료
  • 그리고 visited에 해당 배추 좌표 추가
• 군집 개수 확인
  • 배추 좌표의 개수만큼 loop 돌리고
  • visited에 해당 좌표가 없으면 dfs시작
    • 모든 인접한 좌표 방문처리 완료
  • 그래서 결국, dfs 돌릴 수 있는 시작점의 개수가 몇개인지 파악

import sys
sys.setrecursionlimit(10**6)

def dfs(x, y, cabbages, visited, m, n):
    if (x, y) not in cabbages or (x, y) in visited:
        return
    visited.add((x, y))
    
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    for dx, dy in directions:
        nx, ny = x + dx, y + dy
        if 0 <= nx < m and 0 <= ny < n: 
            dfs(nx, ny, cabbages, visited, m, n)

t = int(input())
for _ in range(t):
    m, n, k = map(int, input().split())
    cabbages = set()
    for _ in range(k):
        x, y = map(int, input().split())
        cabbages.add((x, y))
    
    visited = set()
    network = 0
    
    for x, y in cabbages:
        if (x, y) not in visited:
            dfs(x, y, cabbages, visited, m, n)
            network += 1
    
    print(network)