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

1012번: 유기농 배추

 

 

 

코드

import sys
from collections import deque
dx = [0,0,-1,1]
dy = [-1,1,0,0]

def bfs(x,y):
	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 < n and 0 <= ny < m:
				if worm[nx][ny] == 1:
					worm[nx][ny] = 0
					queue.append((nx,ny))

t = int(input())
for _ in range(t):
	count = 0
	m,n,num = map(int,input().split())
	worm = [[0]*m for _ in range(n)] 
	for _ in range(num):
		x,y = map(int,sys.stdin.readline().split())
		worm[y][x] = 1
	
	for i in range(n):
		for j in range(m):
			if worm[i][j] == 1:
				bfs(i,j)
				count += 1
	print(count)

 

설명

그래프의 칸을 하나씩 돌다가 값이 1인 칸을 발견하면 count를 1만큼 증가시키고 bfs를 수행하여 인접한 칸들을 모두 찾아 값을 0으로 바꿔주었다. 이렇게 하면 해당 구역은 모두 0으로 바껴서 중복되어 세어지지 않는다.