[BOJ] #1012 유기농 배추 (Python)

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

🚀

알고리즘 분류🔗

그래프 이론, 그래프 탐색, BFS, DFS

🚀

문제 설명🔗

가로 M, 세로 N 크기의 배추밭에 배추가 심어져 있습니다.

배추는 1x1 크기로 심어져 있으며, 배추가 심어져 있지 않은 곳은 0으로 표시됩니다.

배추가 심어져 있는 곳은 1로 표시됩니다.

해충을 막기 위해 배추흰지렁이 한 마리를 배추밭에 놓으려고 합니다.

배추흰지렁이는 인접한 배추를 모두 관리할 수 있습니다.

최소 몇 마리의 배추흰지렁이를 놓아야 하는지 구하는 프로그램을 작성하면 됩니다.

#1012 유기농 배추

✅

입력🔗

첫 줄에는 테스트 케이스의 개수 T가 주어집니다.

각 테스트 케이스의 첫 줄에는 배추밭의 가로 M, 세로 N, 배추가 심어져 있는 위치의 개수 K가 차례로 주어집니다.

배추의 위치는 다음 K개의 줄에 주어집니다.

배추의 위치는 (x, y)로 주어지며, x는 가로 좌표, y는 세로 좌표입니다.

(0 ≤ x < M, 0 ≤ y < N)

✅

출력🔗

각 테스트 케이스마다 배추흰지렁이의 최소 개수를 출력합니다.

🚀

풀이🔗

입력으로 주어진 배추밭 정보를 바탕으로 2차원 배열을 만든다.
각 배추 위치를 ground[y][x] = 1로 표시한다.
배추밭 전체를 순회하며 방문하지 않은 배추가 있다면 BFS로 연결된 배추들을 모두 탐색한다.
BFS를 한 번 시작할 때마다 독립된 배추 그룹이므로 지렁이 수를 1 증가시킨다.
모든 그룹 탐색이 끝나면 지렁이 수(count)를 출력한다.

🚀

코드 - Python🔗

import sys
from collections import deque
 
sys.setrecursionlimit(10000)  # DFS 사용 시 재귀 제한 증가 (예방 차원)
 
T = int(sys.stdin.readline())  # 테스트 케이스 수
dx = [0, 0, 1, -1]  # 좌우
dy = [1, -1, 0, 0]  # 상하
 
for _ in range(T):
    M, N, K = map(int, sys.stdin.readline().split())  # 가로(M), 세로(N), 배추 위치 수(K)
    ground = [[0] * M for _ in range(N)]  # 배추밭 초기화 (세로 x 가로)
    visited = [[False] * M for _ in range(N)]  # 방문 체크 배열
 
    for _ in range(K):  # 배추 위치 표시
        x, y = map(int, sys.stdin.readline().split())
        ground[y][x] = 1
 
    # BFS로 연결된 배추 그룹 탐색
    def bfs(y, x):
        queue = deque()
        queue.append((y, x))
        visited[y][x] = True
        while queue:
            cy, cx = queue.popleft()
            for d in range(4):
                ny, nx = cy + dy[d], cx + dx[d]
                if 0 <= ny < N and 0 <= nx < M:
                    if not visited[ny][nx] and ground[ny][nx] == 1:
                        visited[ny][nx] = True
                        queue.append((ny, nx))
 
    count = 0  # 지렁이 수
    for i in range(N):
        for j in range(M):
            if not visited[i][j] and ground[i][j] == 1:
                bfs(i, j)
                count += 1  # 새로운 연결 그룹 발견 시 증가
 
    print(count)

🚀

핵심🔗

✅

그래프 탐색🔗

BFS(너비 우선 탐색) 또는 DFS(깊이 우선 탐색)를 사용하여 연결된 배추를 탐색합니다.
BFS는 큐를 사용하여 구현하며, DFS는 재귀 또는 스택을 사용하여 구현할 수 있습니다.

✅

시간 복잡도🔗

입력 크기:

M x N <= 50 x 50 = 2500, K <= 2500

최악의 경우: 2500개의 배추가 모두 떨어져 있을 때 → O(K)번 BFS 수행

BFS 내부 탐색: 각 칸마다 최대 4번 확인 → O(K x 4) = O(K)

총 시간 복잡도: O(K)

🚀

반례 모음(예제 제외)🔗

answer: 1

answer: 3

answer: 2

추천 포스트

[BOJ] #1012 유기농 배추 (Python)[BOJ] #1012 Organic Cabbage (Python)