@[파이썬] [DFS] 백준 1012 유기농 배추

문제

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

1012번: 유기농 배추

코드

import sys

sys.setrecursionlimit(10000)

t = int(input())

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


def dfs(r, c):
    visited[r][c] = 1
    for i in range(4):
        nx = r + dx[i]
        ny = c + dy[i]
        if 0 <= nx < n and 0 <= ny < m:
            if visited[nx][ny] == 0 and graph[nx][ny] == 1:
                dfs(nx, ny)


for _ in range(t):
    m, n, k = map(int, input().split())

    graph = [[0] * m for _ in range(n)]
    visited = [[0] * m for _ in range(n)]

    for _ in range(k):
        a, b = map(int, input().split())
        graph[b][a] = 1

    count = 0
    for i in range(n):
        for j in range(m):
            if visited[i][j] == 0 and graph[i][j] == 1:
                count += 1
                dfs(i, j)
    print(count)