[BOJ] 1012:유기농 배추

■ 문제풀이

1) dfs 알고리즘

 

■ 해답

import sys
sys.setrecursionlimit(10 ** 8)

def dfs(x, y):
    if x <= -1 or x >= n or y <= -1 or y >= m:
        return False
    
    if graph[x][y] == 1:
        graph[x][y] = 0
        
        # 상, 하, 좌, 우
        dfs(x - 1, y)
        dfs(x + 1, y)
        dfs(x, y - 1)
        dfs(x, y + 1)
        
        return True
    return False

# 테스트 케이스 입력
t = int(input())

result = []
for i in range(t):
    # m = 가로, n = 세로, k = 배추가 심어져 있는 위치의 개수
    m, n, k = map(int, sys.stdin.readline().split())
    
    # 0으로 초기화 후 배추가 있는 곳 1로 변환
    graph = [[0] * m for _ in range(n)]
    for _ in range(k):
        a, b = map(int, sys.stdin.readline().split())
        graph[b][a] = 1
    
    count = 0
    for i in range(n):
        for j in range(m):
            if dfs(i, j) == True:
                count += 1
                
    result.append(count)

for i in result:
    print(i)

출처 : https://www.acmicpc.net/problem/1012

1012번: 유기농 배추