[백준] 1012 유기농 배추

단계별로 풀어보기 DFS와 BFS의 4단계 문제이다

 

1012번: 유기농 배추

3단계 문제인 2667번과 입출력 방법 말고는 거의 같아서 쉽게 풀 수 있었다.

오히려 배추 개수를 출력할 필요가 없어서 더 쉬웠다.

def dfs(row, col):
    if li[row][col] == 0 or visited[row][col]:
        return 0
    stack = []
    stack.append((row, col))
    while stack:
        cur = stack.pop()
        visited[cur[0]][cur[1]] = True
        if li[cur[0] - 1][cur[1]] == 1 and not visited[cur[0] - 1][cur[1]]:
            if 1 <= cur[0] - 1 <= n and 1 <= cur[1] <= m:
                stack.append((cur[0] - 1, cur[1]))
        if li[cur[0] + 1][cur[1]] == 1 and not visited[cur[0] + 1][cur[1]]:
            if 1 <= cur[0] + 1 <= n and 1 <= cur[1] <= m:
                stack.append((cur[0] + 1, cur[1]))
        if li[cur[0]][cur[1] - 1] == 1 and not visited[cur[0]][cur[1] - 1]:
            if 1 <= cur[0] <= n and 1 <= cur[1] - 1 <= m:
                stack.append((cur[0], cur[1] - 1))
        if li[cur[0]][cur[1] + 1] == 1 and not visited[cur[0]][cur[1] + 1]:
            if 1 <= cur[0] <= n and 1 <= cur[1] + 1 <= m:
                stack.append((cur[0], cur[1] + 1))
    return 1

test_case = int(input())
from sys import stdin

for i in range(test_case):
    m, n, k = list(map(int, stdin.readline().split()))
    li = [[0] * m for j in range(n)]
    for j in range(0, k):
        rawInput = list(map(int, stdin.readline().split()))
        li[rawInput[1]][rawInput[0]] = 1
    li.insert(0, [0] * (m + 2))
    li.append([0] * (m + 2))
    for j in range(1, n + 1):
        li[j].insert(0, 0)
    for j in range(1, n + 1):
        li[j].append(0)
    visited = [[False for j in range(m + 2)] for i in range(n + 2)]
    count = 0
    for j in range(1, n + 1):
        for l in range(1, m + 1):
            count += dfs(j, l)
    print(count)