[알고리즘 문제풀이] 유기농 배추

문제 제목 : 유기농 배추

문제 난이도 : 하

문제 유형 : DFS, BFS

https://www.acmicpc.net/problem/1012
시간 제한 : 1초
메모리 제한 : 512MB

문제풀이 아이디어

• 연결요소의 개수를 세는 문제
• 모든 정점에 대해 DFS 또는 BFS를 수행
• 수행한 총 횟수를 계산
• DFS로 문제를 푸는 경우 sys라이브러리의 setrecursionlimit()함수를 사용해야한다.
  -> 재귀 최대 깊이가 기본 설정이 1,000회이기때문에 그 설정을 바꿔주기위해서

< 소스코드 >

import sys
sys.setrecursionlimit(100000)

def dfs(x, y):
    visited[x][y] = True
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    for dx, dy in directions:
        nx, ny = x + dx, y + dy
        if nx < 0 or nx >= n or ny < 0 or ny >= m:
            continue
        if array[nx][ny] and not visited[nx][ny]:
            dfs(nx, ny)

for _ in range(int(input())):
    m, n, k = map(int, input().split())
    array = [[0] * m for _ in range(n)]
    visited = [[False] * m for _ in range(n)]
    for _ in range(k):
        y, x = map(int, input().split())
        array[x][y] = 1
    result = 0
    for i in range(n):
        for j in range(m):
            if array[i][j] and not visited[i][j]:
                dfs(i, j)
                result += 1
    print(result)