악곱 == 악성곱슬

DFS

---

해당 문제는 DFS, BFS 모두 사용 가능하다.

백준 2667번의 단지 번호 붙이기 문제와 유사하다. 2차원 배열 안에서 결국 그룹의 개수를 세야 하는 문제이고, 최단경로를 구하는 문제가 아니므로 DFS, BFS 모두 활용가능하다.

따라서 DFS로 작성한 코드는 다음과 같다.

import sys

def dfs(g, x, y):
    # 인덱스 범위 밖
    if x < 0 or y < 0 or x >= M or y >= N:
        return False
    # 이미 방문 했거나 배추가 없는 곳
    if g[y][x] == 0:
        return False
    # 방문 표시 -> 상하좌우
    g[y][x] = 0
    dfs(g, x - 1, y)
    dfs(g, x + 1, y)
    dfs(g, x, y + 1)
    dfs(g, x, y - 1)
    return True

sys.setrecursionlimit(10000)
T = int(sys.stdin.readline().rstrip())
# 테스트 케이스만큼 반복
for _ in range(T):
    M, N, K = map(int, sys.stdin.readline().rstrip().split())
    graph = [[0] * M for _ in range(N)]
    answer = 0
    for _ in range(K):
        x, y = map(int, sys.stdin.readline().rstrip().split())
        graph[y][x] = 1
    for i in range(M):   # x
        for j in range(N):  # y
            if dfs(graph, i, j) is True:
                answer += 1
    print(answer)