[Python] 백준 알고리즘 #1012 유기농 배추

문제

1012번: 유기농 배추

 

풀이

bfs를 사용해서 간단하게 풀었다.

import sys
from collections import deque

T = int(input())

dr = [-1, 1, 0, 0]
dc = [0, 0, 1, -1]

def bfs(x, y):

    queue = deque()
    queue.append([x,y])
    field[x][y] = 2

    while queue:
        now = queue.popleft()

        for i in range(4):
            ndr = now[0] + dr[i]
            ndc = now[1] + dc[i]

            if ndc >= 0 and ndc < N and ndr >= 0 and ndr < M and field[ndr][ndc] == 1:
                queue.append([ndr, ndc])
                field[ndr][ndc] = 2


#  테스트케이스
for i in range(1, T+1):
    result = 0

    # M : 가로길이 / N : 세로길이  / K : 배추의 개수
    M, N, K = map(int, sys.stdin.readline().split())

    # M * N 사이즈 밭 0으로 초기화
    field = [[0 for _ in range(N)] for _ in range(M)]

    # 인풋 받아서 1로 채우기
    for _ in range(K):
        i, j = map(int, sys.stdin.readline().split())
        field[i][j] = 1

    # 순회하면서 1인애 찾기 -> 걔부터 bfs 시작 (이미 처리된 애들은 2로 바뀌어서 여기 안걸림)
    for i in range(M):
        for j in range(N):
            if field[i][j] == 1:
                result += 1
                bfs(i,j)

    print(result)