[백준 1012] 유기농 배추

0. 제목

• 백준 1012 유기농 배추
• BOJ 1012 유기농 배추
• 파이썬 1012 유기농 배추
• Python 1012 유기농 배추

---

1. 문제

www.acmicpc.net/problem/1012

1012번: 유기농 배추

---

2. 풀이

• 2차원 배열 형태의 문제에서 좌표 입력을 받을 때 (x, y)를 arr[y][x] 로 표현하는 것을 항상 생각하며 푼다.
• 파이썬에서 setrecursionlimit으로 재귀 허용 깊이를 늘려주지 않으면 런타임 오류가 뜨는 경우가 있어, 재귀 허용 깊이를 수동으로 늘려주는 코드를 상단에 적어주어야 한다.
• dfs함수를 선언할 때 좌표의 각 점을 인자로 받는다. 이 문제에서는 상, 하, 좌, 우 만으로 움직일 수 있기 때문에 directions라는 배열에 이동 가능 거리 좌표를 넣고, 다음 좌표(next X, next Y)를 구한다. 
• next X, next Y가 0보다 작거나 주어진 범위를 넘어가면 continue로 해당 차시 반복을 넘어가고 그것이 아니라면 방문해야하는 점이지만 아직 방문하지 않은 점에 대하여 재귀적으로 dfs함수를 실행한다.
• 테스트 케이스마다 개수(result)를 출력해주면 된다.

---

3. 코드

import sys
sys.setrecursionlimit(100000)
 
def dfs(x, y):
    visited[x][y] = True
    directions = [(-1, 0), (0, 1), (1, 0), (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)