책너두 - 알고리즘 챌린지[7/20]

오늘의 문제 : 유기농 배추

오늘 문제는 BFS를 활용해서 풀었다.

8달 전에도 똑같은 문제를 풀어서 괜히 과거의 나와 경쟁심이 생겼다.

그래도 그 때 코드에 비해선 깔끔?해진 것 같다. (사실 크게 다른 건 없다)

import sys
from collections import deque

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

    while q :
        x, y = q.popleft()
        for i in range(4) :
            nx, ny = x + dx[i], y + dy[i]
            if nx < 0 or ny < 0 or nx >= m or ny >= n :
                continue

            if cabagge[ny][nx] == 1 :
                cabagge[ny][nx] = cabagge[y][x]
                q.append((nx, ny))

t = int(sys.stdin.readline())

for _ in range(t) :
    m, n, k = map(int, sys.stdin.readline().split())
    cabagge = [[0] * m for _ in range(n)]
    
    for _ in range(k) :
        c, r = map(int, sys.stdin.readline().split())
        cabagge[r][c] = 1

    cnt = 0
    for i in range(m) :
        for j in range(n) :
            if cabagge[j][i] == 1 :
                cnt += 1
                bfs(i, j)

    print(cnt)