실버2 유기농 배추(1012)

1012번: 유기농 배추

이 문제는 상하좌우를 탐색하면서 연결된 컴포넌트를 다 이어서 그 연결된 컴포넌트가 몇 개인지 구하면 되는 문제였다. 저번에 푼 바이러스문제와 비슷해서 금방 풀 수 있었다.

import sys
from collections import deque
input = sys.stdin.readline

directions = [(-1, 0), (0, -1), (1, 0), (0, 1)]

def bfs(x, y, matrix):
    queue = deque([(x, y)])
    matrix[x][y] = 0
    while queue:
        s = queue.popleft()
        for d in directions:
            if (0<=s[0]+d[0]<n and 0<=s[1]+d[1]<m) and (matrix[s[0]+d[0]][s[1]+d[1]]):
                queue.append((s[0]+d[0],s[1]+d[1]))
                matrix[s[0]+d[0]][s[1]+d[1]] = 0

for _ in range(int(input())):
    cnt = 0
    n, m, k = map(int, input().split())
    matrix = [[0]*m for _ in range(n)]
    for _ in range(k):
        x, y = map(int, input().split())
        matrix[x][y] = 1
    for i in range(n):
        for j in range(m):
            if matrix[i][j]:
                cnt += 1
                bfs(i, j, matrix)
    print(cnt)

위와 같이 구현을 했다. 테스트케이스를 여러개로 할 수 있어서 매번 전체 매트릭스가 입력이 될 때마다 전체 매트릭스를 탐색했다. 1이면 BFS를 실행하여 연결된 컴포넌트를 0으로 만들었다. 1이 발견되면 카운트를 하나씩 올려서 계산하고 마지막에 출력했다.