[백준] 1012번:유기농 배추 (python 파이썬)

문제

www.acmicpc.net/problem/1012

1012번: 유기농 배추

풀이

dfs로 풀어줬다.

sys.setrecursionlimit(100000) 안해주면 재귀오류? 뜸

 

소스코드

from collections import deque
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline

def dfs(y, x):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    arr[y][x] = 0
    for i in range(4):
        nowx, nowy = dx[i]+x, dy[i]+y
        if 0<=nowx<m and 0<=nowy<n and arr[nowy][nowx]:
            dfs(nowy, nowx)

    
t = int(input())
for _ in range(t):
    m, n, k = map(int, input().split())
    arr = [[0]*(m) for _ in range(n)]
    for i in range(k):
        a, b = map(int, input().split())
        arr[b][a]=1
    cnt = 0
    for i in range(n):
        for j in range(m):
            if arr[i][j]==1:
                cnt += 1
                dfs(i, j)
    print(cnt)