백준 : 유기농 배추 - 1012

입력

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 첫째 줄에는 배추를 심은 배추밭의 가로길이 M(1 ≤ M ≤ 50)과 세로길이 N(1 ≤ N ≤ 50), 그리고 배추가 심어져 있는 위치의 개수 K(1 ≤ K ≤ 2500)이 주어진다. 그 다음 K줄에는 배추의 위치 X(0 ≤ X ≤ M-1), Y(0 ≤ Y ≤ N-1)가 주어진다. 두 배추의 위치가 같은 경우는 없다.

출력

각 테스트 케이스에 대해 필요한 최소의 배추흰지렁이 마리 수를 출력한다.

예제 입력 1 

2
10 8 17
0 0
1 0
1 1
4 2
4 3
4 5
2 4
3 4
7 4
8 4
9 4
7 5
8 5
9 5
7 6
8 6
9 6
10 10 1
5 5

예제 출력 1 

5
1

예제 입력 2 

1
5 3 6
0 2
1 2
2 2
3 2
4 2
4 0

예제 출력 2 

2

 

이 문제는 기존에 풀었던 음료수 얼려 먹기와 거의 동일하였다. 다만 주의할 점으로는 x,y의 형태가 수학적으로 주는 좌표는 프로그래밍 행렬과는 반대로 표시되어야 한다는 점이다. 이를 유의하여 문제를 풀어야만 한다!

 

from collections import deque
import sys

# 재귀 깊이 제한 해제
sys.setrecursionlimit(100000)

def dfs(x, y):
    # 1. 경계 조건 확인: 밭의 범위를 벗어났을 경우
    if x < 0 or x >= m or y < 0 or y >= n:
        return

    # 2. 방문 여부 & 배추 유무 확인: 배추가 없거나 이미 방문했다면 탐색 중단
    if graph[y][x] == 0:
        return

    # 3. 방문 처리: 현재 위치의 배추를 0으로 바꿔 다시 세지 않도록 함
    graph[y][x] = 0

    # 4. 상하좌우 탐색 (재귀 호출)
    dfs(x-1, y)
    dfs(x+1, y)
    dfs(x, y-1)
    dfs(x, y+1)

t = int(input())

for _ in range(t):
    m, n, k = map(int, input().split())

    graph = [[0] * m for _ in range(n)]

    for _ in range(k):
        x, y = map(int, input().split())
        graph[y][x] = 1

    result = 0

    # 2차원 배열을 순회하며 배추 덩어리 찾기
    for y in range(n):  # y 좌표 (세로)
        for x in range(m): # x 좌표 (가로)
            if graph[y][x] == 1:
                dfs(x, y)
                result += 1

    print(result)