백준 1012 유기농 배추 - 파이썬

문제.

풀이.

BFS를 이용하여 1을 만나면 BFS를 실행하고 방문한곳은 0을 처리해준다 한번 BFS가 끝나면 배추흰지렁이의 갯수를 +1 해준다.

 

소스코드.

import sys

def BFS(y, x):
    queue = [[y, x]]
    while queue:
        a, b = queue[0][0], queue[0][1]
        del queue[0]
        for i in range(4):
            ny = a+dx[i]
            nx = b+dy[i]
            if 0 <= ny < N and 0 <= nx < M and matrix[ny][nx] == 1:
                matrix[ny][nx] = 0
                queue.append([ny, nx])

tc = int(sys.stdin.readline())
dx = [1, -1, 0, 0]
dy = [0, 0, -1, 1]
for i in range(tc):
    M, N, K = map(int, sys.stdin.readline().split())
    matrix = [[0 for i in range(M)] for j in range(N)]
    cnt = 0
    for j in range(K):
        X, Y = map(int, sys.stdin.readline().split())
        matrix[Y][X] = 1

    for y in range(N):
        for x in range(M):
            if matrix[y][x] == 1:
                BFS(y, x)
                matrix[y][x] = 0
                cnt +=1
    print(cnt)