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

문제를 해석해보니 BFS 문제라는 것을 느꼈습니다.

내가 생각한 Solution

문제에서 생각해볼 점

• 너무 전형적인 BFS라서 딱히 설명을 드릴게 없네요...

• 구름 문제 유형이라고 군집의 개수를 찾는 부류의 문제입니다.

• 아래 그림을 참고 하세요.

코드 구현

import sys
from collections import deque

T = int(input())

for tc in range(T):
    M, N, K = map(int, sys.stdin.readline().split())
    ground = [[0] * M for _ in range(N)]
    total_q = [[] for _ in range(K)]
    for i in range(K):
        X, Y = map(int, sys.stdin.readline().split())
        ground[Y][X] = 1
        total_q[i] = [X, Y]
    
    # BFS는 queue 자료구조를 활용하니까 deque 사용을 추천!
    total_q = deque(total_q)
    result = 0
    while total_q:
        c, r = total_q.popleft()
        
        # 아직 탐색되지 않은 구역이라면
        if ground[r][c] == 1:
            ground[r][c] = 0
            tmp_q = deque([[r, c]])
            
            # 해당 칸을 시발점으로 주변 탐색 고우...(BFS)
            while tmp_q:
                r, c = tmp_q.popleft()
                for dc, dr in [[0, 1], [1, 0], [-1, 0], [0, -1]]:
                    if 0 <= c + dc < M and 0 <= r + dr < N:
                        if ground[r+dr][c+dc]:
                            tmp_q.append([r+dr, c+dc])
                            ground[r+dr][c+dc] = 0
            result += 1
    print(result)