알고리즘: 백준 1012번 유기농 배추 (feat. python)

1012번: 유기농 배추

 

 

import sys
read = sys.stdin.readline

case = int(read())

def sol():
    global count
    count = 0
    
    m, n, bae = list(map(int, read().split()))
    box = [[0 for _ in range(m)] for _ in range(n)]

    for _ in range(bae):
        x, y = list(map(int, read().split()))
        box[y][x] = 1
    
    for i in range(n):
        for j in range(m):
            dfs(j, i, m, n, box)
    print(count)

def check(x, y, m, n, box):
    if 0 <= x < m and 0 <= y < n and box[y][x] == 1:
        return True
    return False


def dfs(start_x, start_y, m, n, box):
    global count
    if not check(start_x, start_y, m, n, box):
        return
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    sx = [start_x]
    sy = [start_y]
    count += 1
    while sx:
        cx = sx.pop()
        cy = sy.pop()
        for i in range(4):
            if check(cx + dx[i], cy+dy[i], m, n, box):
                sx.append(cx + dx[i])
                sy.append(cy + dy[i])
                box[cy + dy[i]][cx + dx[i]] = 0

for _ in range(case):
    sol()