Yunsu's Log

BOJ 1012: 유기농 배추

10 min read

Note

2D 그리드에서 연결된 컴포넌트 찾기 기법을 활용하여 BFS로 해결하는 문제입니다.

문제

차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있는 것이다.

한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어 놓았다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다.

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

입력

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 첫째 줄에는 배추를 심은 배추밭의 가로길이 M(1 ≤ M ≤ 50)과 세로길이 N(1 ≤ N ≤ 50), 그리고 배추가 심어져 있는 위치의 개수 K(1 ≤ K ≤ 2500)이 주어진다. 그 다음 K줄에는 배추의 위치 X(0 ≤ X ≤ M-1), Y(0 ≤ Y ≤ N-1)가 주어진다. 두 배추의 위치가 같은 경우는 없다.

출력

각 테스트 케이스에 대해 필요한 최소의 배추흰지렁이 마리 수를 출력한다.

예제

예제 입력 1:

2
10 8 17
0 0
1 0
1 1
4 2
4 3
4 5
2 4
3 4
7 4
8 4
9 4
7 5
8 5
9 5
7 6
8 6
9 6
10 10 1
5 5

예제 출력 1:

5
1

문제 분석

이 문제는 2D 그리드에서 연결된 컴포넌트를 찾는 문제입니다. 배추가 심어진 위치(1)가 상하좌우로 연결되어 있으면 하나의 그룹으로 간주하고, 각 그룹마다 배추흰지렁이가 한 마리씩 필요합니다.

핵심 포인트

  1. 2D 그리드: M × N 크기의 그리드
  2. 상하좌우 연결: 인접한 배추는 하나의 그룹
  3. 연결된 컴포넌트 개수: 그룹의 개수가 필요한 지렁이의 수
  4. 좌표 주의: X가 열(가로), Y가 행(세로) - grid[Y][X] 형태

해결 방법

BFS를 사용하여 연결된 컴포넌트를 찾습니다:

  1. 그리드를 초기화하고 배추 위치를 1로 표시
  2. 모든 셀을 순회하며 배추(1)를 발견하면 BFS 시작
  3. BFS로 상하좌우로 연결된 모든 배추를 탐색하고 0으로 변경
  4. 연결된 컴포넌트의 개수를 세어 출력

코드 구현

제공된 코드

from collections import deque
import sys
 
readline = sys.stdin.readline
 
tc = int(readline())
 
for _ in range(tc):
    m, n, k = map(int, readline().rstrip().split())
    
    grid: list[list[int]] = [[0 for _ in range(m)] for _ in range(n)]
    kQueue: deque[(int, int)] = deque()
    visitQueue: deque[(int, int)] = deque()
    
    # 배추 칸을 1로 설정
    for _ in range(k):
        x, y = map(int, readline().rstrip().split())
        grid[y][x] = 1
        kQueue.append((y, x))
    
    result = 0
    while kQueue:
        k = kQueue.popleft()
        visitQueue.append(k)
 
        if grid[k[0]][k[1]] == 1:
            result += 1
        else:
            visitQueue.popleft()
            continue
 
        while visitQueue:
            v = visitQueue.popleft()
            y = v[0]
            x = v[1]
 
            # 상하좌우 1이면 집어넣기.
            # 상
            if y > 0:
                up = grid[y - 1][x]
                if up == 1:
                    visitQueue.append((y - 1, x))
                    grid[y - 1][x] = 0
            # 하
            if y < n - 1:
                down = grid[y + 1][x]
                if down == 1:
                    visitQueue.append((y + 1, x))
                    grid[y + 1][x] = 0
 
            # 좌
            if x > 0:
                down = grid[y][x - 1]
                if down == 1:
                    visitQueue.append((y, x - 1))
                    grid[y][x - 1] = 0
 
            # 우
            if x < m - 1:
                down = grid[y][x + 1]
                if down == 1:
                    visitQueue.append((y, x + 1))
                    grid[y][x + 1] = 0
 
    print(result)

코드 분석

1. 입력 처리

from collections import deque
import sys
 
readline = sys.stdin.readline
 
tc = int(readline())
  • 입력 최적화를 위해 sys.stdin.readline() 사용
  • 테스트 케이스 개수를 입력받음

2. 그리드 초기화

m, n, k = map(int, readline().rstrip().split())
grid: list[list[int]] = [[0 for _ in range(m)] for _ in range(n)]
  • M × N 크기의 그리드를 0으로 초기화
  • grid[y][x] 형태로 접근 (Y가 행, X가 열)

3. 배추 위치 표시

for _ in range(k):
    x, y = map(int, readline().rstrip().split())
    grid[y][x] = 1
    kQueue.append((y, x))
  • 배추가 심어진 위치를 1로 표시
  • 배추 위치를 큐에 저장 (나중에 탐색용)

4. BFS로 연결된 컴포넌트 찾기

result = 0
while kQueue:
    k = kQueue.popleft()
    visitQueue.append(k)
 
    if grid[k[0]][k[1]] == 1:
        result += 1
    else:
        visitQueue.popleft()
        continue
 
    while visitQueue:
        v = visitQueue.popleft()
        y = v[0]
        x = v[1]
 
        # 상하좌우 탐색
        # ...

자세한 설명은 BFS 알고리즘 포스트를 참고하세요.

개선된 코드

더 명확하고 효율적으로 작성한다면:

from collections import deque
import sys
 
readline = sys.stdin.readline
 
def count_components(grid, n, m):
    count = 0
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # 상, 하, 좌, 우
    
    for i in range(n):
        for j in range(m):
            if grid[i][j] == 1:
                count += 1
                
                # BFS로 연결된 모든 배추 탐색
                queue = deque([(i, j)])
                grid[i][j] = 0  # 방문 표시
                
                while queue:
                    y, x = queue.popleft()
                    
                    for dy, dx in directions:
                        ny, nx = y + dy, x + dx
                        
                        if 0 <= ny < n and 0 <= nx < m:
                            if grid[ny][nx] == 1:
                                grid[ny][nx] = 0  # 방문 표시
                                queue.append((ny, nx))
    
    return count
 
tc = int(readline())
 
for _ in range(tc):
    m, n, k = map(int, readline().rstrip().split())
    grid = [[0] * m for _ in range(n)]
    
    # 배추 위치 표시
    for _ in range(k):
        x, y = map(int, readline().rstrip().split())
        grid[y][x] = 1
    
    print(count_components(grid, n, m))

개선 사항:

  • 함수로 분리하여 가독성 향상
  • 방향 벡터를 배열로 정의하여 코드 간결화
  • 불필요한 큐 제거 (kQueue, visitQueue → 하나의 queue)
  • 그리드를 직접 수정하여 visited 배열 불필요

시간 및 공간 복잡도

시간 복잡도

  • 그리드 초기화: O(N × M)
  • BFS 탐색: O(N × M) - 모든 셀을 최대 한 번씩 방문
  • 전체: O(T × N × M) - T는 테스트 케이스 개수

공간 복잡도

  • 그리드 저장: O(N × M)
  • BFS 큐: O(N × M) - 최악의 경우 (모든 배추가 연결된 경우)
  • 전체: O(N × M)

예제 동작 과정

예제 입력 1: 첫 번째 테스트 케이스

그리드 (10 × 8):

배추 위치가 표시된 그리드

BFS 탐색 과정:

  1. (0, 0)에서 시작 → 컴포넌트 1 발견
    • (0,0), (1,0), (1,1) 탐색
  2. (2, 4)에서 시작 → 컴포넌트 2 발견
    • (2,4), (3,4), (4,2), (4,3), (4,5) 탐색
  3. (4, 7)에서 시작 → 컴포넌트 3 발견
    • (4,7), (4,8), (4,9), (5,7), (5,8), (5,9), (6,7), (6,8), (6,9) 탐색
  4. (4, 2)에서 시작 → 이미 방문함 (컴포넌트 2에 포함)
  5. … (나머지 배추들도 이미 방문됨)

결과: 5개의 컴포넌트

주의사항

1. 좌표 순서

문제에서 X, Y 순서로 주어지지만, 그리드는 grid[Y][X] 형태로 접근해야 합니다:

  • X: 열(가로, column)
  • Y: 행(세로, row)

2. 경계 체크

상하좌우로 이동할 때 항상 경계를 체크해야 합니다:

if 0 <= ny < n and 0 <= nx < m:
    # 유효한 범위

3. 방문 표시

그리드를 직접 수정하여 방문 표시를 하면 별도의 visited 배열이 필요 없습니다:

grid[y][x] = 0  # 방문 표시

관련 알고리즘

그래프 뷰

백링크