백준 1012번 유기농 배추

문제:
한나는 고랭지에서 유기농 배추를 재배하며 해충 방지를 위해 흰지렁이를 이용한다. 상하좌우로 인접한 배추 묶음을 하나의 그룹으로 보고, 각 그룹마다 지렁이 한 마리씩 필요하다.

입력:
- 첫 줄: 테스트케이스 수 T
- 각 테스트케이스: - 1줄: 배추밭의 가로길이 M, 세로길이 N, 배추의 개수 K - 이후 K줄: 각 배추의 좌표 X, Y

출력:
- 필요한 최소 지렁이 수 출력

import sys
sys.setrecursionlimit(10000)

def find(x, y):
    visited[y][x] = True
    dx = [0, 0, -1, 1]
    dy = [-1, 1, 0, 0]

    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < M and 0 <= ny < N:
            if graph[ny][nx] == 1 and not visited[ny][nx]:
                find(nx, ny)

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

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

    worm = 0
    for j in range(N):
        for i in range(M):
            if graph[j][i] == 1 and not visited[j][i]:
                find(i, j)
                worm += 1
    print(worm)

맨 위로 이동