[백준][python]1012 유기농배추

문제

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

소스코드

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

if __name__ == "__main__":
    t = int(input())
    for _ in range(t):
        n,m,b = map(int,input().split())
        arr = [[-1] * m for _ in range(n)] #땅 -1로 초기화
        q = deque()
        for _ in range(b):
            x,y = map(int,input().split())
            arr[x][y] = 0 #배추가 있는 곳 0으로 초기화
        dx = [1,-1,0,0]
        dy = [0,0,1,-1]
        cnt = 0
        for i in range(n):
            for j in range(m):
                if arr[i][j] == 0: #배추가 있는 곳이면
                    cnt +=1 #지렁이 1마리 추가 (누적)
                    q.append([i,j])
                    while q: #상하좌우 체크 같은 지역은 같은 지렁이 공유
                        x,y = q.popleft()
                        for k in range(4):
                            xx = x + dx[k]
                            yy = y + dy[k]
                            if 0<=xx<n and 0<=yy<m and arr[xx][yy] == 0: #배추가 있다
                                arr[xx][yy] = -1 #체크
                                q.append([xx,yy])
                    
        print(cnt)

설명

아파트 단지수 체크하는 로직이 떠올랐다

BFS를 이용해서 같은 지역에 지렁이를 1개씩 추가해줬다