[BOJ] 1012. 유기농 배추

📌 문제 제목

문제 링크: BOJ 1012

---

🗒️ 문제 설명

배추밭에 배추흰지렁이를 둬서 해충을 잡아먹게 하려고 한다.

배추흰지렁이는 인접한 다른 배추로 이동할 수 있다.

배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 된다.

총 몇 마리의 지렁이가 필요한 지 출력하라.

시간 제한: 1초

메모리 제한: 512MB

1 <= M <= 50

1 <= N <= 50

1 <= K <= 2,500

---

💡 문제 해결 아이디어

• BFS를 한번 돌 때 인접한 배추를 다 돌기 때문에 BFS 한번에 지렁이 한 마리가 필요.

---

⌛️ 시간 복잡도

• O(T x (N x M + K))

---

✅ 최종 코드

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

T = int(input().strip())

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


def bfs(graph, x, y, visited, N, M):
    queue = deque([(x, y)])
    visited[x][y] = True
    while queue:
        xp, yp = queue.popleft()
        for dx, dy in direction:
            nx, ny = xp + dx, yp + dy
            if not (0 <= nx < N and 0 <= ny < M):
                continue
            if graph[nx][ny] == 1 and not visited[nx][ny]:
                queue.append((nx, ny))
                visited[nx][ny] = True


for _ in range(T):
    M, N, K = map(int, input().split())

    graph = [[0] * M for _ in range(N)]
    visited = [[False] * M for _ in range(N)]

    for _ in range(K):
        Y, X = map(int, input().split())
        graph[X][Y] = 1

    answer = 0
    for i in range(N):
        for j in range(M):
            if graph[i][j] == 1 and not visited[i][j]:
                bfs(graph, i, j, visited, N, M)
                answer += 1
    print(answer)