[백준] 1012 | 유기농 배추 [파이썬/python]

문제

link: https://www.acmicpc.net/problem/1012

배추밭에 필요한 배추흰지렁이 수 최솟값을 출력하는 문제이다.

 

접근

배추흰지렁이가 인접한 배추로는 이동할 수 있으므로, 배추들이 몇 군데에 퍼져있는지를 확인하면 된다.

DFS를 이용했다. set에 좌표값을 저장하여, 특정 땅의 좌표를 제거할 때 인접한 좌표도 함께 제거하는 식으로 몇 군데에 퍼져있는지를 세어 주었다.

재귀 함수를 이용했기 때문에, 재귀 깊이 제한을 조정하는 코드를 추가했다.

 

코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000)

def search(x, y):
    if (x, y) not in s:
        return
    s.discard((x, y))
    if x != 0:
        search(x-1, y)
    if x != M-1:
        search(x+1, y)
    if y != 0:
        search(x, y-1)
    if y != N-1:
        search(x, y+1)

for _ in range(int(input())):
    M, N, K = map(int, input().split())
    cnt = 0
    s = set(tuple(map(int, input().split())) for _ in range(K))
    while s:
        x, y = next(iter(s))
        search(x, y)
        cnt += 1
    print(cnt)