1012 유기농 배추

문제

해당 배열에서 1의 응집 지역을 찾는 문제이다.

Link: 유기농 배추

코드

import sys
sys.setrecursionlimit(10 ** 4)
num_of_problem = int(sys.stdin.readline())
data = []
valid = []
width, height = 0, 0

def dfs(h, w):
    if(h < 0 or  h > height-1):
        return 0
    if (w < 0 or w > width - 1):
        return 0
    if(data[h][w] == 0):
        return 0
    else:
        data[h][w] = 0
        return 1 + dfs(h, w+1)+ dfs(h, w-1) + dfs(h+1, w) + dfs(h-1, w)

for i in range(num_of_problem):
    width, height, num_of_cabage = map(int, sys.stdin.readline().split())
    cnt = 0
    data = [[0 for j in range(width)] for i in range(height)]

    for j in range(num_of_cabage):
        w, h = map(int, sys.stdin.readline().split())
        data[h][w] = 1
    for h in range(0, height):
        for w in range(0, width):
            if(data[h][w] == 0):
                continue
            dfs(h, w)
            cnt += 1
    print(cnt)

풀이

데이터를 입력 받은 후,
2중으로 for문을 돌면서 data[j][k]가 1인지 검사한다.

만약 1인 경우에는 상하좌우의 값까지 검사하도록 재귀를 이용해서 짰다.

dfs 함수에서는 index 의 범위가 올바른지 보고 값을 검사한다.