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

 

배추들이 상하좌우로 인접해있는 곳에는 배추흰지렁이가 한 마리만 있어도 되기 때문에

모든 배추들이 탐색완료가 될 때까지 BFS나 DFS를 수행하고

그 횟수를 세주면 되는 간단한 문제다.

 

평소엔 행을 x로 열을 y로 두고 푸는 경우가 많은데 이 문제에선 반대라서

그게 좀 헷갈렸다.

 

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

def bfs(ay,bx):
    q = deque()
    q.append((ay,bx))
    visited[ay][bx] = True
    while q:
        y,x = q.popleft()
        for i in range(4):
            ny = y+dy[i]
            nx = x+dx[i]
            if 0<=ny<N and 0<=nx<M:
                if not visited[ny][nx] and graph[ny][nx]==1:
                    q.append((ny,nx))
                    visited[ny][nx] = True

T = int(input())
dx = [-1,1,0,0]
dy = [0,0,-1,1]
for i in range(T):
    M,N,K = map(int,input().split())
    # 배추밭 생성
    graph = [[0 for _ in range(M)]for _ in range(N)]
    # 방문체크를 위한 리스트
    visited = [[False for _ in range(M)]for _ in range(N)]

	# BFS 탐색횟수를 저장하는 변수
    cnt = 0
    # 배추의 위치를 입력받고 그래프에 1로 표기함
    for _ in range(K):
        x,y = map(int,input().split())
        graph[y][x] = 1
    # 그래프에서 미방문한 배추가 있다면 BFS를 수행하고 cnt를 1 증가시킴
    for j in range(N):
        for k in range(M):
            if graph[j][k]==1 and not visited[j][k]:
                bfs(j,k)
                
                cnt +=1
    print(cnt)