Note
문제
차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있는 것이다.
한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어 놓았다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다.
문제 링크: https://www.acmicpc.net/problem/1012
알고리즘 이론: 2D 그리드에서 연결된 컴포넌트 찾기
2차원 배열(그리드)에서 특정 조건(예: 값이 1)을 만족하는 셀들이 상하좌우로 인접해 있을 때, 이를 하나의 **연결된 컴포넌트(Connected Component)**로 봅니다.
1. 상하좌우 탐색 패턴 (Direction Vectors)
그리드에서 특정 위치 의 인접한 칸을 탐색할 때, 방향 벡터를 정의하여 반복문으로 처리하는 것이 깔끔합니다.
# 상, 하, 좌, 우 순서의 변화량
dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]
# 또는 튜플 리스트 사용
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
for i in range(4):
ny = y + dy[i]
nx = x + dx[i]
# 다음 위치 (ny, nx) 처리2. 유효 범위 체크 (Boundary Check)
새로운 좌표 가 그리드 범위를 벗어나지 않는지 반드시 확인해야 합니다.
3. 방문 표시 (Visiting)
이미 탐색한 셀을 다시 탐색하지 않도록 표시해야 무한 루프를 방지하고 정확한 컴포넌트 개수를 셀 수 있습니다.
- 방법 1: 별도의
visited2차원 배열 사용 - 방법 2: 원본
grid의 값을 변경 (예: 1을 0으로 수정)
해결 방법
- 크기의 그리드를 생성하고 배추 위치를
1로 표시합니다. - 그리드의 모든 칸을 순회하며 배추(
1)가 있는 칸을 찾습니다. - 배추를 발견하면 **지렁이 수(count)**를 1 증가시키고, 해당 칸에서 BFS 또는 DFS를 시작합니다.
- 탐색 과정에서 만나는 연결된 모든 배추를
0으로 바꿔 다시 방문하지 않게 합니다. - 모든 칸에 대한 순회가 끝나면 최종
count를 출력합니다.
코드 구현
Python 구현 (BFS 방식)
import sys
from collections import deque
input = sys.stdin.read
def solve():
data = input().split()
if not data: return
ptr = 0
t = int(data[ptr]); ptr += 1
results = []
for _ in range(t):
m = int(data[ptr]); ptr += 1
n = int(data[ptr]); ptr += 1
k = int(data[ptr]); ptr += 1
grid = [[0] * m for _ in range(n)]
for _ in range(k):
x = int(data[ptr]); ptr += 1
y = int(data[ptr]); ptr += 1
grid[y][x] = 1
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 and grid[ny][nx] == 1:
grid[ny][nx] = 0
queue.append((ny, nx))
results.append(str(count))
print('\n'.join(results))
if __name__ == "__main__":
solve()시간 및 공간 복잡도
- 시간 복잡도:
- 각 테스트 케이스마다 그리드의 모든 셀을 최대 한 번씩 방문하므로 그리드 크기에 비례합니다.
- 공간 복잡도:
- 그리드 저장 공간과 BFS 큐(최악의 경우 모든 셀이 큐에 들어감)를 위한 공간이 필요합니다.
주의사항
- 좌표 체계: 문제에서 가 가로(열), 가 세로(행)로 주어지므로
grid[Y][X]순서로 접근해야 런타임 에러를 방지할 수 있습니다. - 재귀 제한: DFS(재귀)로 구현할 경우 파이썬의 기본 재귀 깊이 제한()을 초과할 수 있으므로
sys.setrecursionlimit()을 사용하거나 BFS를 권장합니다. - 입력 최적화: 테스트 케이스가 많고 이 크면
sys.stdin.readline이나sys.stdin.read().split()을 사용하는 것이 좋습니다.