[BOJ / Python] 1012번: 유기농 배추

문제: BOJ 1012번

풀이

배추가 붙어있는게 몇 세트가 있는지 물어보는 문제이다.
모든 칸을 다 돌면서 탐색하지 않았다면 그 부분을 DFS돌리고, 카운트를 1씩 올린다면 총 덩어리 수가 확인 될 것이다.

최종코드

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6) #재귀 한계 설정
d=[[0,1],[0,-1],[1,0],[-1,0]]


def dfs(x, y): #DFS 함수.
    vis[y][x] = 1
    for dx,dy in d:
        if 0 <= y + dy < n and 0 <= x + dx < m and ar[y + dy][x + dx] == 1 and vis[y + dy][x + dx] == 0:
            dfs(x + dx, y + dy)


t = int(input())
for _ in range(t):
    cnt = 0
    m, n, k = map(int, input().split())
    ar = [[0 for _ in range(m)] for _ in range(n)]
    for _ in range(k):    #배추의 위치 입력받기
        x, y = map(int, input().split())
        ar[y][x] = 1        
    vis = [[0 for _ in range(m)] for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if ar[i][j] == 1 and vis[i][j] == 0:    #방문하지 않은 배추 탐색
                dfs(j, i)       #이어져 있는 부분을 모두 탐색하기때문에 한 뭉치만 탐색하게 된다.
                cnt += 1        #덩어리 수 카운트
    print(cnt)

파이썬에서 재귀를 사용할 때 sys.setrecursionlimit()은 무조건 해줘야한다. 파이썬 기본 재귀 깊이는 1000정도로 매우 얕기 때문이다.