BOJ 1012 유기농 배추

https://www.acmicpc.net/problem/1012
시간 1초, 메모리 512MB
input :

• 테스트 케이스의 개수 T
• 가로 길이 M, 세로길이 N, 배추가 심어져 있는 위치의 개수 K(1 <= M, N <= 50)(1 <= K <= 2,500)
• 배추의 위치X, Y(0 <= X <= M - 1),(0 <= Y <= N - 1)

output :

• 최소의 배추흰지렁이 마리 수를 출력.

조건 :

• 배추의 상하좌우에 다른 배추가 위치한 경우에 서로 인접해있다고 간주.
• 배추들의 모임을 개수를 세자.
• 배추가 있는 1, 없는 0

---

BOJ 4963 섬의 개수와 동일한 풀이를 가질 거라 예상되는 문제.

필요한 변수.
빈 그래프(배추의 위치를 표시), visit은 필요없음 그래프의 1과 0으로 표시
DFS에 들어가는 횟수 세아릴 cnt 변수.
BFS로도 풀수 있지만 금방 DFS로 풀었기에 DFS로 풀자.

필요한 함수.
DFS 함수.(1인 것들을 0으로 바꿔주자.)

정답 코드 :

import sys
sys.setrecursionlimit(10000)

T = int(sys.stdin.readline())
ans = []

def DFS(navi, position):
    navi[position[0]][position[1]] = 0

    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]

    for i in range(len(dx)):
        nx = position[0] + dx[i]
        ny = position[1] + dy[i]
        if nx >= n or nx < 0 or ny >= m or ny < 0:
            continue
        if navi[nx][ny]:
            DFS(navi, [nx, ny])

for _ in range(T):
    m, n, k = map(int, sys.stdin.readline().split())
    graph = [[0] * m for _ in range(n)]

    for i in range(k):
        y, x = map(int, sys.stdin.readline().split())
        graph[x][y] = 1

    cnt = 0

    for x in range(n):
        for y in range(m):
            if graph[x][y]:
                DFS(graph, [x, y])
                cnt += 1

    ans.append(cnt)

for data in ans:
    print(data)