[BaekJoon] 1012 유기농 배추

▶ 문제 :

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

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

import sys

t = int(input())
sys.setrecursionlimit(10**6)

def dfs(a, b):
    if a < 0 or a >= m or b < 0 or b >= n:
        return

    if graph[a][b] == 0:
        return

    graph[a][b] = 0
    dfs(a - 1, b)
    dfs(a, b - 1)
    dfs(a + 1, b)
    dfs(a, b + 1) 

for _ in range(t):
    m, n, k = map(int, input().split())

    graph = [[0 for _ in range(n)]for _ in range(m)]

    for _ in range(k):
        a, b = map(int, input().split())
        graph[a][b] = 1
    
    result = 0
    for a in range(m):
        for b in range(n):
            if graph[a][b] == 1:
                dfs(a,b)
                result += 1

    print(result)

 

▶ 문제풀이 

 

1. dfs() 선언 => 배열의 범위를 벗어나거나 해당 칸의 값이 0이면 반환 아닌 경우엔 해당 칸과 인접하면서 1을 가진 칸을 0으로 변환

2. graph데이터를 순회하며 1값을 가진 칸을 찾아 해당 칸과 인접한 1들을 0으로 변환

3. 탐색 종료시 1을 가진 군집을 0으로 변환할 때의 횟수를 센 result 값을 출력