[백준][Python] 1012번 유기농 배추

DFS 풀이

import sys
sys.setrecursionlimit(10000)
def dfs(x,y):
    
    if x <= -1 or x >= n or y <= -1 or y >= m:
        return False
    
    if matrix[x][y] == 1:
        
        matrix[x][y] = 0
        
        dfs(x + 1, y)
        dfs(x - 1, y)
        dfs(x, y + 1)
        dfs(x, y - 1)
        return True
    return False

t = int(input())
for _ in range(t):
    
    m,n,k = map(int,input().split())
    matrix = [[0]*m for i in range(n)]
    for i in range(k):
        a,b = map(int,input().split())
        matrix[b][a] = 1


    result = 0
    for i in range(n):
        for j in range(m):
        
            if dfs(i, j) == True:
            
                result += 1
    print(result)

BFS 풀이

from collections import deque

def bfs(x,y):
    
    queue = deque()
    queue.append((x,y))
    graph[x][y] = 0
    count = 1
    while queue:
        x,y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if nx <= -1 or nx >= n or ny <= -1 or ny >= m:
                continue
            if graph[nx][ny] ==0:
                continue
            
            if graph[nx][ny] == 1:
                queue.append((nx,ny))
                graph[nx][ny] = 0
                count += 1
    return count

t = int(input())

for _ in range(t):

    m,n,k = map(int,input().split())
    graph = [[0] * m for i in range(n)]
    for i in range(k):
        a,b = map(int,input().split())
        graph[b][a] = 1
    
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]
    
    
    cnt = []
    for i in range(n):
        for j in range(m):
            
            if graph[i][j] == 1:
                cnt.append(bfs(i,j))    
    print(len(cnt))