백준 1012: 유기농 배추 (Python)

 

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

1012번: 유기농 배추

 

pypy3로 제출함. 드디어 dfs와 bfs가 익숙해졌따......!

 

# dfs

def dfs(x, y):
    if x < 0 or x >= m or y < 0 or y >= n:
        return False
    if list[y][x] == 1:
        list[y][x] = 0
        dfs(x+1, y)
        dfs(x-1, y)
        dfs(x, y+1)
        dfs(x, y-1)
        return True
    else:
        return False

t = int(input())
count = []

for i in range(t):
    m, n, k = map(int, input().split())
    list = [[0] * m for _ in range(n)]
    count.append(0)

    for j in range(k):
        x, y = map(int, input().split())
        list[y][x] = 1

    for a in range(n):
        for b in range(m):
            if dfs(b, a):
                count[i] += 1

for i in range(t):
    print(count[i])

# bfs

from collections import deque

def bfs(x, y):
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    queue = deque()

    if list[y][x] == 1:
        queue.append([y, x])
        list[y][x] = 0

        while queue:
            q1, q2 = queue.popleft()

            for i in range(4):
                mx = q2 + dx[i]
                my = q1 + dy[i]

                if mx < 0 or mx >= m or my < 0 or my >= n:
                    continue

                if list[my][mx] == 1:
                    queue.append([my, mx])
                    list[my][mx] = 0
        return True
    else:
        return False

t = int(input())
count = []

for i in range(t):
    m, n, k = map(int, input().split())
    list = [[0] * m for _ in range(n)]
    count.append(0)

    for j in range(k):
        x, y = map(int, input().split())
        list[y][x] = 1

    for a in range(n):
        for b in range(m):
            if bfs(b, a):
                count[i] += 1

for i in range(t):
    print(count[i])