백준 1012 유기농 배추

문제

유기농 배추

bfs를 이용해 필요한 지렁이의 수를 구하자

난이도 : Silver2

---

풀이

1. 간단히 bfs를 이용해 문제 풀이

---

코드

import sys
from collections import deque


def bfs(point):
    q = deque([point])
    farm[q[0][0]][q[0][1]] = 0  # start point 탐색 완료
    
    while q:  # 더 이상 큐에서 탐색할 부분이 없으면 종료
        p = q.popleft()  # 배추가 심어진 지대
        for i in range(4):  # 상하좌우 네 방향을 모두 탐색
            c, r = p
            nc = c + directions[i][0]
            nr = r + directions[i][1]

            if 0 <= nc < M and 0 <= nr < N:  # 상하좌우 탐색 시 범위를 벗어나지 않게
                if farm[nc][nr] == 1:  # 배추가 심어져 있는 지대라면,
                    farm[nc][nr] = 0  # 0으로 만들어 다시 탐색하지 않아도 되게 만듦
                    q.append((nc, nr))  # 1인 지점만 탐색하면 되므로 1일 때만 큐에 추가


directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
T = int(sys.stdin.readline())

for _ in range(T):
    M, N, K = tuple(map(int, sys.stdin.readline().split()))
    farm = [[0 for _ in range(N)] for _ in range(M)]
    cabbages = []
    
    for _ in range(K):
        i, j = tuple(map(int, sys.stdin.readline().split()))
        farm[i][j] = 1  # 배추가 심어져 있으면 1로
        cabbages.append((i, j))  # 배추가 심어진 지점들을 저장
    
    worm = 0  # 필요 지렁이 개수
    for cabbage in cabbages:  # 모든 배추가 심어진 지점들을 탐색
        if farm[cabbage[0]][cabbage[1]] == 1:  # 지렁이가 안전 지대로 만든 배추 구역은 탐색하지 않음
            bfs(cabbage)  # 배추가 심어진 부분(1)을 넘겨주며 bfs로 안전 지대 전파
            worm += 1
        
    print(worm)