(Python) - BOJ(1012번) : 유기농 배추

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

1012번: 유기농 배추

 

• 해설 :

0과 1로 이루어진 2차원 배열이 주어진다. 유기농 배추를 재배하기 위해  1들의 군집(인접한 1들의 집합)마다 배추흰지렁이 한 마리를 방생한다고 할 때, 총 몇 마리가 필요한지 찾는 문제이다.

 

 

 

 

:

• 풀이 :

BFS 또는 DFS로 해결할 수 있는 문제이다. 나는 BFS로 해결하였다. for문으로 배열의 모든 원소를 탐색하며 1인 원소(배추)를 만날 때마다 인접한 모든 원소를, 탐색하고 카운트를 1 증가시켜준다. 모든 원소를 탐색할 때까지 진행하면 된다.

 

 

 

 

dy = [0,0,-1,1]
dx = [-1,1,0,0]
# 상, 하, 좌, 우
 
 
 
def bfs(j,k):
    queue = [[j,k]]
    while queue:
        a, b = queue[0][0],queue[0][1]
        field[a][b] = 0
        del queue[0]
 
        for i in range(4):
            j = a + dx[i]
            k = b + dy[i]
 
            if 0 <= j < M and 0 <= k < N and field[j][k] == 1:
                field[j][k] = 0
                queue.append([j,k])
 
 
if __name__ == "__main__":
    testCase = int(input())
 
    for _ in range(testCase):
        M,N,K = map(int,input().split())
        cnt = 0
        field = [[0]*N for _ in range(M)]
        for _ in range(K):
            j,k = map(int,input().split())
            field[j][k] = 1
        for j in range(M):
            for k in range(N):
                if field[j][k] == 1:
                    bfs(j,k)
                    cnt +=1
        print(cnt)