1. 문제 설명

유기농 배추

2. 문제 분석

그래프 내 클러스터의 개수를 탐색 알고리즘으로 카운트한다.

1. 이동 가능한 노드가 1, 그렇지 않으면 0으로 표시된 그래프가 존재한다.
2. 클러스터, 즉 이동 가능한 노드 집합의 개수를 카운트한다.
3. 모든 좌표에서 시작, 1로 표시된 이동 가능한 노드를 시작 노드로 정하자.
4. 탐색 알고리즘을 통해 이 시작 노드에서 이동 가능한 모든 노드를 탐색한다.
5. 더 이상 이동할 노드가 없다면, 그래프에 남아 있는 다른 노드를 탐색해 클러스터의 개수를 카운트한다.

• 탐색 알고리즘을 사용하는 것보다 행과 열로 이 그래프를 만드는 과정이 더 헷갈렸다. x축이 열, y가 행으로 표시되고 다음 좌표(즉 오프셋을 더한 다음 노드의 좌푯값)가 주어진 리스트 인덱스에 유효한지 체크하는 데 m(열의 길이)이 아니라 무심코 n(행의 길이)를 두 번 써버려서 원하는 결과가 나오지 않아 헤맸다. 주의하자.

3. 나의 풀이

t = int(input())
for _ in range(t):
    m, n, k = map(int, input().split())
    # row N col M
    nodes = [[0 for _ in range(m)] for _ in range(n)]
    for _ in range(k):
        col, row = map(int, input().split())
        nodes[row][col] = 1
    queue = []
    cnt = 0
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    # 상화좌우 이동할 때 현재 좌표 row, col에 각각 더할 offset
    for i in range(n):
        for j in range(m):
            if nodes[i][j] == 1:
                queue.append([i, j])
                # 순서대로 이동하며 이동 가능 노드를 시작 노드로 선택
                while queue:
                    row, col = queue.pop(0)
                    nodes[row][col] = 0
                    # 방문 노드를 0으로 마크
                    for x, y in zip(dx, dy):
                        next_row, next_col = row+x, col+y
                        # 상하좌우 이동 시 이동 가능한지 확인
                        if next_row < 0 or next_col < 0 or next_row > n-1 or next_col > m-1: continue

                        # 이동 시 연결 노드가 있다면 큐에 넣고 0으로 마킹
                        if nodes[next_row][next_col] == 1:
                            queue.append([next_row, next_col])
                            nodes[next_row][next_col] = 0
                cnt += 1
                # 클러스터의 개수만 파악한다.
    print(cnt)