백준 1012 파이썬 (유기농 배추)

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

💻 Code (DFS)

import sys
sys.setrecursionlimit(10000)    # 재귀 깊이 설정

dx = [-1, 1, 0, 0]  # 방향벡터
dy = [0, 0, -1, 1]

def dfs(x, y):
    if x <= -1 or x >= N or y <= -1 or y >= M:
        return False
    if farm[x][y] == 1:
        farm[x][y] = 0  # 방문처리
        for i in range(4):  # 상하좌우 방문
            dfs(x + dx[i], y + dy[i])
        return True
    return False


T = int(input())
for _ in range(T):
    M, N, K = map(int, input().split())
    farm = [[0] * M for _ in range(N)]

    for _ in range(K):
        x, y = map(int, input().split())
        farm[y][x] = 1
    
    cnt = 0     
    for i in range(N):
        for j in range(M):
            if dfs(i, j):
                cnt += 1
    print(cnt)

• sys.setrecursionlimit(10000) : 백준에서는 재귀의 최대 깊이가 1000으로 설정 되어있어서 그냥 제출할경우 RecursionError가 발생한다. 따라서 재귀 깊이를 설정해주자
• for i in range(4): dfs(x + dx[i], y + dy[i])
  방향벡터를 미리 설정후 상하좌우를 방문한다.
  ex) x, y = 1, 1
  (0,1), (2,1), (1,0), (1,2)
  -return True : 상하좌우는 재귀적으로 방문만 할뿐 (표시용) 아무튼간에 한 칸이라도 방문에 성공하면 True를 return 한다.