백준 1012 유기농 배추

유기농 배추

풀이 계획

• BFS든 DFS든 써서 인접한 배추 무더기 개수 구하기
• DFS 쓸 것임
• 방문한 곳은 0으로 변경하기

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
tc = int(input())

# 상 우 하 좌
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

def dfs(x, y):
    # 유효 범위 확인
    if x < 0 or x >= m or y < 0 or y >= n:
        return False
    # 방문한 적 없는 곳이면
    if map_lst[y][x] == 1:
        map_lst[y][x] = 0
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            dfs(nx, ny)
        return True
    return False

for _ in range(tc):
    m, n, k = map(int, input().split())
    map_lst = []
    ans = 0
    # 입력 받기
    for _ in range(n):
        map_lst.append([0] * m)
    for _ in range(k):
        x, y = map(int, input().split())
        map_lst[y][x] = 1
    # 계산
    for i in range(m):
        for j in range(n):
            res = dfs(i, j)
            if res:
                ans += 1
    # 출력
    print(ans)

• sys.setrecursionlimit 해주기!