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

 

 

 

2중 for문으로 배열을 돌면서 1을 만나면, 카운트를 세며 bfs를 통해 인접한 모든 1을 0으로 만들어서 다시 접근 하지 않도록 하였다.

 

from collections import deque
TC = int(input())

for tc in range(1,TC+1):
    M,N,V = map(int,input().split())
    cnt = 0
    arr = [[0] * M for _ in range(N)]
    for i in range(V):
        x,y = map(int,input().split())
        arr[y][x] = 1

    def bfs(y,x):
    
        q = deque([(y,x)])
        
        while q:
            y,x = q.popleft()

            directy = [0,0,1,-1]
            directx = [1,-1,0,0]

            for k in range(4):
                dy = directy[k] + y
                dx = directx[k] + x

                if dy >= N or dy < 0 or dx >= M or dx < 0: # 배열을 벗어난다면 continue
                    continue
                    
                if arr[dy][dx] == 1: # 인접한 배열중에 1이 있다면 0으로 바꿔줌
                    arr[dy][dx] = 0
                    q.append([dy,dx])

    for j in range(N):
        for i in range(M):
            if arr[j][i] == 1: # 1을 만난다면 cnt를 세주면서 본인을 0으로 바꿔주고 bfs 시작
                cnt += 1 
                arr[j][i] = 0
                bfs(j,i)

    print(cnt)