백준 1012번 유기농 배추 - python

문제 링크 : https://www.acmicpc.net/problem/1012

📌 문제 분류: 자료구조, 그래프 탐색
📦 알고리즘: BFS (너비 우선 탐색)
🎯 난이도: 실버 2

📌 문제 설명

어떤 배추밭에 배추가 심어져 있을 때, 서로 인접한 배추들이 하나의 지렁이로 방제될 수 있다고 한다. 지렁이 최소 수를 구하라는 문제.

• 상하좌우 인접한 배추는 하나의 무리로 간주
• 무리 수 = 지렁이 수

💡 접근 방식

이 문제는 결국 연결 요소 개수를 구하는 전형적인 그래프 탐색 문제이다.

왜 BFS를 선택했나?

• DFS는 재귀 깊이가 깊어질 경우 런타임 에러 발생 가능
• BFS는 Queue 기반 탐색으로 안정적이며, Python에서는 큰 입력에도 적합

풀이 과정

1. M × N 크기의 그래프 생성
2. 배추가 있는 좌표에 1 표시
3. 아직 방문하지 않은 1에서 BFS 탐색 시작
4. 탐색할 때마다 count += 1 → 하나의 배추 무리

풀이 코드 (BFS)

from collections import deque

# 상하좌우 이동
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(x, y):
    queue = deque()
    queue.append((x, y))
    visited[x][y] = True

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if not visited[nx][ny] and graph[nx][ny] == 1:
                    visited[nx][ny] = True
                    queue.append((nx, ny))

# 테스트 케이스 개수
T = int(input())

for _ in range(T):
    m, n, k = map(int, input().split())
    graph = [[0] * m for _ in range(n)]
    visited = [[False] * m for _ in range(n)]

    for _ in range(k):
        x, y = map(int, input().split())
        graph[y][x] = 1

    count = 0
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 1 and not visited[i][j]:
                bfs(i, j)
                count += 1

    print(count)

✨ 핵심 포인트 정리

• BFS는 deque 사용으로 빠르고 메모리 효율적
• DFS보다 런타임 에러 발생 가능성 적음
• 그래프에서 연결된 컴포넌트 개수 세기 문제 유형

🗂️ 관련 키워드

그래프 탐색, BFS, 연결 요소 개수, 실버2, Python, deque, 지렁이, 유기농 배추, DFS vs BFS

DFS 풀이 (재귀 방식)

DFS도 문제 해결이 가능하지만, 재귀 깊이 제한에 유의해야 한다.

DFS 코드

import sys
sys.setrecursionlimit(10000)  # 재귀 깊이 제한 해제

# 상하좌우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def dfs(x, y):
    visited[x][y] = True
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < n and 0 <= ny < m:
            if not visited[nx][ny] and graph[nx][ny] == 1:
                dfs(nx, ny)

# 테스트 케이스 수
T = int(input())

for _ in range(T):
    m, n, k = map(int, input().split())
    graph = [[0] * m for _ in range(n)]
    visited = [[False] * m for _ in range(n)]

    for _ in range(k):
        x, y = map(int, input().split())
        graph[y][x] = 1

    count = 0
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 1 and not visited[i][j]:
                dfs(i, j)
                count += 1

    print(count)

✍️ 마무리 정리

• BFS와 DFS 모두 풀이 가능하지만, 입력이 큰 경우엔 BFS가 유리
• DFS는 sys.setrecursionlimit() 호출이 필요함