[백준] 1012 (실버2)

이 문제는 상하좌우로 인접해있는 1의 묶음 개수를 세는 것이다.
각 지점에서 dfs 혹은 bfs를 통해 방문처리는 1 -> 0으로 바꾸는 것으로 하여 그래프를 탐색하면 된다.
각 지점에서 dfs 혹은 bfs가 끝날 때마다 count를 하나씩 올려준다.

import sys
sys.setrecursionlimit(100000)


def dfs(x, y):
    # 주어진 범위를 벗어나는 경우에는 즉시 종료
    if x <= -1 or x >= n or y <= -1 or y >= m:
        return False
    # 현재 노드를 아직 방문하지 않았다면
    if graph[x][y] == 1:
        # 해당 노드 방문 처리
        graph[x][y] = 0
        # 상, 하, 좌, 우의 위치들도 모두 재귀적으로 호출
        dfs(x - 1, y)
        dfs(x, y - 1)
        dfs(x + 1, y)
        dfs(x, y + 1)
        return True
    return False


t = int(input())
test = [0 for _ in range(t)]
for x in range(t):
    n, m, count = map(int, input().split())

    # 배추밭 그림
    graph = [[0] * m for _ in range(n)]
    for _ in range(count):
        a, b = map(int, input().split())
        graph[a][b] = 1

    for i in range(n):
        for j in range(m):
            # 현재 위치에서 dfs 수행
            if dfs(i, j):
                test[x] += 1

for i in range(t):
    print(test[i], end='\n')

dfs 함수는 인접한 곳을 모두 둘러본 뒤 true 혹은 false를 return 한다.
false인 경우는 아예 범위 밖으로 나가버렸거나, 배추가 없는 곳이거나, 이미 방문한 곳이다.