[Python] 1012: 유기농 배추

문제:
어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다.
한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있는 것.
-> 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되는 것.

배추가 심어져 있는 위치를 알 때, 필요한 최소 배추흰지렁이의 수를 출력.

풀이:

# 유기농 배추 (silver 2)

# dfs 사용 - 재귀로 구현
def dfs(x, y, N, M):
    dx = [0, 0, -1, 1] # 방향 설정 한 칸 씩.
    dy = [-1, 1, 0, 0]
    if (x >= 0 and x < N and y >= 0 and y < M): 
        if (visited[x][y] == 0 and farm[x][y] == 1): # 방문 안 했고 배추가 있는 곳
            visited[x][y] = 1 # 방문처리 해 주고
            for i in range(4): 
                x_ = x + dx[i]
                y_ = y + dy[i]
                dfs(x_, y_, N, M) # 그 위치 기준 상하좌우 다 방문해서 방문처리 해주기
        else: # 방문 했거나 배추가 없는 곳
            return # 해서 dfs 탈출
    else: # 배추밭의 범위를 벗어난 곳
        return # 마찬가지로 dfs 탈출

T = int(input())
ans = []

for test in range(T):
    M, N, K = map(int, input().split())
    farm = [[0]* M for i in range(N)] # 먼저 배추밭을 다 0으로 초기화

    for cabbage in range(K): # 입력받은 배추의 위치에 따라 배추밭의 그 부분을 1로 만들어 줌.
        X, Y = map(int, input().split())
        farm[Y][X] = 1
    
    visited = [[0]* M for i in range(N)] # 방문 여부의 배추밭과 같은 크기의 2차원 리스트 생성, 0으로 초기화
    worm_num = 0 # 배추흰지렁이의 수
    #dfs
    for n in range(N):
        for m in range(M):
            if (farm[n][m] == 1 and visited[n][m] == 0): # 밭의 [0][0]부터 오른쪽으로 쭉 훑으면서 
                dfs(n, m, N, M) # dfs를 통해 인접한 배추들을 모두 방문처리
                worm_num += 1 # 그리고 그 구역 당 지렁이 한 마리 필요하므로 +1을 해 줌.
    
    ans.append(worm_num) # 각 테스트케이스마다 지렁이 수가 필요하므로 ans 리스트에 appdend

for i in range(len(ans)):
    print(ans[i])