230224 [1012: 유기농배추]

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

#DFS 풀이

import sys
from collections import deque
sys.setrecursionlimit(1000000)

def DFS(x, y):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    for i in range(4):
        nowx = x + dx[i]
        nowy = y + dy[i]

        if (0<=nowx<N) and (0<=nowy<M):
            if graph[nowx][nowy] == 1:
                graph[nowx][nowy] = -1
                DFS(nowx, nowy)              

input = sys.stdin.readline
T = int(input().rstrip())

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

    #배추 위치에 1표
    for j in range(K):
        X, Y = map(int, input().rstrip().split())
        graph[Y][X] = 1

    for x in range(M):
        for y in range(N):
            if graph[y][x] == 1:
                DFS(y, x)
                cnt+=1
    print(cnt)

# BFS 풀이

import sys
from collections import deque
sys.setrecursionlimit(1000000)

def BFS(a, b):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    queue = deque()
    queue.append((a,b))
    graph[a][b] = 0

    while queue:
        x,y = queue.popleft()
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if 0<=nx<N and 0<=ny<M:
                if graph[nx][ny] ==1:
                    graph[nx][ny] = -1
                    queue.append((nx,ny))

input = sys.stdin.readline
T = int(input().rstrip())

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

    #배추 위치에 1표
    for j in range(K):
        X, Y = map(int, input().rstrip().split())
        graph[Y][X] = 1

    for x in range(M):
        for y in range(N):
            if graph[y][x] == 1:
                #DFS(y, x)
                BFS(y, x)
                cnt+=1
    print(cnt)