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

문제

https://www.acmicpc.net/problem/1012

1012번: 유기농 배추

문제 해결방법

bfs 로 해결 가능

graph[y][x] == 1 인 곳에서 검색을 시작하여
인접한 부분을 모두 0으로 변경한 뒤에 count++

문제 풀이

import sys
from collections import deque

T = int(sys.stdin.readline().strip())
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

for _ in range(T):
    M, N, K = map(int, sys.stdin.readline().strip().split())
    graph = [[0] * M for _ in range(N)]
    for _ in range(K):
        x, y = map(int, sys.stdin.readline().strip().split())
        graph[y][x] = 1


    def bfs(x, y):
        queue = deque()
        queue.append((x, y))
        graph[y][x] = 0

        while queue:
            x, y = queue.popleft()
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if nx < 0 or nx >= M or ny < 0 or ny >= N:
                    continue
                if graph[ny][nx] == 1:
                    graph[ny][nx] = 0
                    queue.append((nx, ny))
        return 1


    count = 0
    for i in range(M):
        for j in range(N):
            if graph[j][i] == 1:
                count += dfs(i, j)

    print(count)