출처: https://www.acmicpc.net/problem/1012
문제
차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있는 것이다.
한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어 놓았다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다. 예를 들어 배추밭이 아래와 같이 구성되어 있으면 최소 5마리의 배추흰지렁이가 필요하다. 0은 배추가 심어져 있지 않은 땅이고, 1은 배추가 심어져 있는 땅을 나타낸다.
1 1 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 1 1 0 0 0 1 1 1
0 0 0 0 1 0 0 1 1 1
입력
입력의 첫 줄에는 테스트 케이스의 개수 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
예제 입력 2
1
5 3 6
0 2
1 2
2 2
3 2
4 2
4 0
예제 출력 2
2
내가 한 풀이
import sys
# 재귀 한도를 늘려주어야 RecursionError를 방지할 수 있습니다.
sys.setrecursionlimit(10000)
def dfs(x, y, m, n, graph):
# 상, 하, 좌, 우 방향 설정
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
# 현재 위치 방문 처리 (배추를 0으로 만들어 다시 방문 안 하게 함)
graph[y][x] = 0
# 네 방향 확인
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
# 지도 범위 내에 있고, 그곳에 배추(1)가 있다면 더 깊이 탐색
if (0 <= nx < m) and (0 <= ny < n):
if graph[ny][nx] == 1:
dfs(nx, ny, m, n, graph)
# 1. 테스트 케이스 개수 입력
t = int(sys.stdin.readline())
for _ in range(t):
# 2. 가로(m), 세로(n), 배추 개수(k) 입력
m, n, k = map(int(sys.stdin.readline().split()))
# 3. 지도 초기화 (0으로 가득 찬 n x m 배열)
graph = [[0] * m for _ in range(n)]
count = 0
# 4. 배추 위치 입력받아 지도에 표시
for _ in range(k):
a, b = map(int(sys.stdin.readline().split()))
graph[b][a] = 1 # 가로가 a, 세로가 b이므로 graph[b][a]
# 5. 지도 전체를 순회하며 배추 덩어리 찾기
for i in range(m):
for j in range(n):
if graph[j][i] == 1: # 배추를 발견하면
dfs(i, j, m, n, graph) # 탐색 시작 (인접한 배추 다 지우기)
count += 1 # 덩어리 하나 추가
print(count)트러블 슈팅
런타임에러가 뜬다.
최악의 경우 배추가 2500개(50x50)가 모두 연결되어 있다면 재귀 호출이 2500번 발생할 수 있다. 하지만 더 큰 문제는 Python의 기본 재귀 제한과 스택 메모리 문제다.
해결방법 1 재귀 한도 높이기
import sys
sys.setrecursionlimit(100000) # 더 큰 값으로 설정
def dfs(x, y, m, n, graph):
# 상, 하, 좌, 우 방향 설정
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
# 현재 위치 방문 처리 (배추를 0으로 만들어 다시 방문 안 하게 함)
graph[y][x] = 0
# 네 방향 확인
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
# 지도 범위 내에 있고, 그곳에 배추(1)가 있다면 더 깊이 탐색
if (0 <= nx < m) and (0 <= ny < n):
if graph[ny][nx] == 1:
dfs(nx, ny, m, n, graph)
# 1. 테스트 케이스 개수 입력
t = int(sys.stdin.readline())
for _ in range(t):
# 2. 가로(m), 세로(n), 배추 개수(k) 입력
m, n, k = map(int, sys.stdin.readline().split())
# 3. 지도 초기화 (0으로 가득 찬 n x m 배열)
graph = [[0] * m for _ in range(n)]
count = 0
for _ in range(k):
a, b = map(int, sys.stdin.readline().split())
graph[b][a] = 1 # 가로가 a, 세로가 b이므로 graph[b][a]
# 5. 지도 전체를 순회하며 배추 덩어리 찾기
for i in range(m):
for j in range(n):
if graph[j][i] == 1: # 배추를 발견하면
dfs(i, j, m, n, graph) # 탐색 시작 (인접한 배추 다 지우기)
count += 1
print(count)해결방법2: 스택으로 변경
import sys
def dfs(x, y, m, n, graph):
stack = [(x, y)]
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
while stack:
cx, cy = stack.pop()
# 이미 방문했다면 스킵
if graph[cy][cx] == 0:
continue
graph[cy][cx] = 0
for i in range(4):
nx = cx + dx[i]
ny = cy + dy[i]
if (0 <= nx < m) and (0 <= ny < n):
if graph[ny][nx] == 1:
stack.append((nx, ny))
t = int(sys.stdin.readline())
for _ in range(t):
m, n, k = map(int, sys.stdin.readline().split())
graph = [[0] * m for _ in range(n)]
count = 0
for _ in range(k):
a, b = map(int, sys.stdin.readline().split())
graph[b][a] = 1
# 5. 지도 전체를 순회하며 배추 덩어리 찾기
for i in range(m):
for j in range(n):
if graph[j][i] == 1: # 배추를 발견하면
dfs(i, j, m, n, graph) # 탐색 시작 (인접한 배추 다 지우기)
count += 1 # 덩어리 하나 추가
print(count)