[Python] 백준1012번 : 유기농 배추

💡문제

백준 1012번 문제 링크

🍀풀이

이 문제는 학원에서 수업을 듣고, 자바로 풀어본적 있는 문제이다.
방문여부를 체크해서 지렁이 개수를 카운트 해주면 된다.

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

t = int(input().rstrip())

dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]

def bfs(x, y, visited, graph):
    visited[x][y] = 1
    queue = deque()
    queue.append([x, y])
    
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < m and 0 <= ny < n and visited[nx][ny] == 0 and graph[nx][ny] == 1:
                queue.append([nx, ny])
                visited[nx][ny] = 1
    return

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