[BOJ] 파이썬 - 1012 유기농 배추

문제 링크 : https://www.acmicpc.net/problem/1012

파이썬 코드

import sys
from collections import deque

T=int(sys.stdin.readline())


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

def bfs(x,y):
    q=deque()
    q.append([x,y])

    while q:
        x,y=q.popleft()
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if 0<=nx<N and 0<=ny<M and martix[nx][ny]==1:
                martix[nx][ny]=0
                q.append([nx,ny])

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

    martix=[[0]*M for _ in range(N)]

    for i in range(K):
        x,y=map(int,sys.stdin.readline().split())
        martix[y][x]=1

    cnt=0

    for i in range(N):
        for j in range(M):
            if martix[i][j]==1:
                bfs(i,j)
                cnt+=1

    print(cnt)

상하좌우로 1이 인접해 있으면 그 구역당 한 마리의 배추흰지렁이가 필요하다.

즉, martix를 순회하다가 1인 곳을 발견하면 그 곳을 시작노드로하는 bfs를 실행시킨다. 상하좌우로 인접한 노드를 차례대로 큐에 삽입해서 순회하며 모두 0으로 바꿔주고 cnt, 즉 배추 흰지렁이의 수를 1 증가시켜주면 된다.