[백준/파이썬]1012 유기농 배추

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

1012번: 유기농 배추

문제

백준 1012번 유기농 배추

상하좌우 1이 인접한 뭉치가 몇 개나 있는지 구하는 문제다.

 

BFS/DFS문제는 처음 풀어본다.

 

https://www.youtube.com/watch?v=e7_H8SLZlHY 

 

때문에 여기서 나오는 첫번째 문제에서 힌트를 많이 얻었다.

 

BFS로도 풀어보려고 했는데 BFS는 아직 이해가 되지 않는다.

 

정답

 

import sys
sys.setrecursionlimit(10000) 

def dfs(x2, y2) :
    if x2 <= -1 or x2 >= m or y2 <= -1 or y2 >= n :
        return False
    if arr[x2][y2] == 1 :
        arr[x2][y2] = 0
        dfs(x2-1, y2)
        dfs(x2+1, y2)
        dfs(x2, y2-1)
        dfs(x2, y2+1)
        return True
    return False

t = int(sys.stdin.readline().rstrip())
for i in range(t) :
    ans = 0
    m, n, k = map(int, sys.stdin.readline().rstrip().split())
    arr = [[0 for _ in range(n)] for _ in range(m)]
    for j in range(k) :
        x, y = map(int, sys.stdin.readline().rstrip().split())
        arr[x][y] = 1

    for j in range(n) :
        for k in range(m) :
            if dfs(k,j) :
                ans += 1
    
    print(ans)