백준 - 유기농 배추

설명

• 연결된 그래프 개수 찾기
• dfs, stack으로 구현

과정

1. 배추가 심어져 있는 index를 찾고 dfs 시작

• 4 방향으로 인덱스가 넘지 않고, 배추가 심어져 있는지(인접 행렬이 1인지) 확인
• 맞다면 인접 행렬의 요소를 0으로 바꾸고, 스택에 푸시

2. dfs를 마치고 왔다면 그래프 개수를 세는 cnt 1 증가

풀이

from sys import stdin

t = input()

def solution():
    m, n, k = map(int, stdin.readline().split())
    matrix = [[0 for _ in range(n)] for _ in range(m)]

    for i in range(k):
        a, b = map(int, stdin.readline().split())
        matrix[a][b] = 1

    def dfs(sx, sy):
        stack = [(sx, sy)]

        dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
        while stack:
            a, b = stack.pop()

            for i in range(4):
                nx, ny = a + dx[i], b + dy[i]
                if 0 <= nx < m and 0 <= ny < n and matrix[nx][ny] == 1:
                    matrix[nx][ny] = 0
                    stack.append((nx, ny))

    cnt = 0
    for i in range(m):
        for j in range(n):
            if matrix[i][j] == 1:
                dfs(i, j)
                cnt += 1

    print(cnt)

for _ in range(int(t)):
    solution()