[Boj] 유기농 배추 1012(python)

문제링크 : https://www.acmicpc.net/problem/1012

오늘부터 DFS, BFS 문제 시작

입력의 첫 줄에는 테스트 케이스의 개수 N가 주어지며. 그 다음 줄부터 각각의 테스트 케이스에 대해 첫째 줄에는

배추밭의 가로 길이과 세로길이, 그리고 배추가 심어져 있는 총 갯수가 주어짐. 그 다음 K줄에는 배추의 구체적인 위치가 주어짐.

matrix에 배추가 심어져 있는 곳은 1로 배정하고 배추가 심어져 있는 곳에서 DFS함수를 실행함

필자는 보통 DFS를 사용할 때 이런 형태로 많이 사용하며, index 범위를 벗어났을 때에는 그대로 return을 하고

배추가 심어진 곳에서는 0으로 바꾸고, 좌표를 변경하여 DFS를 실행함.

이때, 주의할 점은 sys.setrecursionlimit(10**8) 안할시 오류가 생길 수 있음

결국, DFS나 BFS로 풀 수 있는 문제이며, 필자는 DFS를 선택

import sys
sys.setrecursionlimit(10**8)

def DFS(x, y):
    if x < 0 or x>= row or y >= col or y< 0:
        return
    if 0 <=x < row and 0 <= y < col and matrix[x][y] == 1:
        matrix[x][y] = 0
        DFS(x+1, y)
        DFS(x-1, y)
        DFS(x, y+1)
        DFS(x, y-1)
    return


N = int(input())
for _ in range(N):
    col, row, num = map(int, input().split())
    matrix = [[0] * col for _ in range(row)]
    for _ in range(num):
        tmp_col, tmp_row = map(int, input().split())
        matrix[tmp_row][tmp_col] = 1
    answer = 0
    for current_row in range(row):
        for current_col in range(col):
            if matrix[current_row][current_col]:
                DFS(current_row, current_col)
                answer += 1
    print(answer)