[Graph] 1012번 - 유기농 배추(34일차)

#코드 실행 시간 단축
import sys
input = sys.stdin.readline

#배추밭의 개수
length = int(input())

#배추 군집을 탐색하기 위한 dfs 함수(배추밭, y좌표, x좌표, y좌표 최대값, x좌표 최대값, 배추 군집 번호)
def dfs(cabbage, y, x, y_len, x_len, number):

    #좌상우하 탐색을 위한 좌표 선언
    dy = [0, -1, 0, 1]
    dx = [-1, 0, 1, 0]

    #stack에 탐색 시작 지점을 추가
    stack = [[y,x]]

    #더이상 탐색 지점이 남아 있지 않을 때까지 반복
    while stack:
        #stack에서 가장 최신의 탐색지점을 pop
        index = stack.pop()
        #해당 탐색지점 좌표의 visit을 배추 군집 번호로 저장
        visit[index[0]][index[1]] = number
        #좌상우하에 대해
        for i in range(4):
            #새로운 y,x좌표를 좌상우하 탐색 좌표값을 적용해 선언
            ny = index[0] + dy[i]
            nx = index[1] + dx[i]
            #새로운 y,x좌표가 배추밭의 범위 내에 있을 때
            if(0 <= ny < y_len and 0 <= nx < x_len):
                #새로운 y,x좌표가 방문된 적이 없고, 배추가 있을 때
                if(visit[ny][nx] == 0 and cabbage[ny][nx] == 1):
                    #해당 좌표를 새로운 탐색지점으로 추가
                    stack.append([ny,nx])

#각 배추밭에 대해 반복
for i in range(length):
    #배추밭의 x길이 y길이, 배추 개수를 입력
    m, n, k = map(int, input().split())
    #배추 군집의 수를 세는 변수
    cnt = 0
    #배추밭과 방문기록 2차원 list 선언
    cabbage = [[0 for _ in range(m)] for _ in range(n)]
    visit = [[0 for _ in range(m)] for _ in range(n)]

    #배추 위치를 입력받고 배추밭에 기록
    for j in range(k):
        x, y = map(int, input().split())
        cabbage[y][x] = 1

    #배추밭의 모든 위치에 대해
    for a in range(n):
        for b in range(m):
            #배추가 있고 방문된 적이 없으면
            if(visit[a][b] == 0 and cabbage[a][b] == 1):
                #배추 군집의 수를 추가하고
                cnt += 1
                #해당 위치 기준으로 dfs 탐색
                dfs(cabbage, a, b, n, m, cnt)

    #배추 군집의 개수(지렁이가 필요한 수) 출력
    print(cnt)

#인사이트
#2차원 방문기록 list와 dfs를 활용해 간단하게 풀이할 수 있는 graph 문제
#기본적인 탐색 + 군집의 개수 count가 더해져서 counting을 위한 변수를 선언하고
#방문기록에 Count를 저장함으로써 디버깅 시 군집이 제대로 탐색되었는지 확인하였음