문제
문제 이해
- 배추 흰 지렁이를 배추 근처에 두고 배추를 보호하려고 함
- 지렁이는 인접(상하좌우)한 배추로 이동할 수 있음
- 최소 배추 흰 지렁이 마리 수 출력
- 테스트 케이스 개수 T, 가로 길이 M, 세로 길이 N, 배추가 심어져 있는 위치의 개수 K, 배추의 위치 X, Y
- 입력 조건 : 1 <= N, M <= 50, 1 <= K <= 2500, 0 <= X <= M - 1, 0 <= Y <= N - 1
풀이
DFS (깊이 우선 탐색)을 사용해서 모든 땅을 순회하며, 배추가 존재하는 영역을 카운트
공부했던 '이것이 취업을 위한 코딩 테스트다 with 파이썬'의 DFS 예시와 비슷한 풀이로 구현이 가능
- 입력 조건에 맞게 t, m, n, k, graph(배추밭), x, y 입력
- dfs 함수 구현
- 밭의 범위를 넘어가면 False
- 밭의 범위 내에 있고 배추가 있으면, 다시 상하좌우로 이동하여 배추가 있는지 확인
- 모든 땅을 순회하며 dfs 수행 및 지렁이 수 count
코드
- BOJ 채점 서버에서 최대 재귀 깊이는 1,000으로 설정되어 있음 (BOJ RecursionError)
- 하지만 최대 깊이가 2,500 이상이므로 여유롭게 3000으로 재설정
import sys
sys.setrecursionlimit(3000)
def dfs(x, y):
if x < 0 or x >= n or y < 0 or y >= m:
return False
if graph[x][y] == 1:
graph[x][y] = 0
dfs(x - 1, y)
dfs(x + 1, y)
dfs(x, y - 1)
dfs(x, y + 1)
return True
return False
t = int(input())
for i in range(t):
m, n, k = map(int, input().split())
graph = [[0] * m for _ in range(n)]
count = 0
for j in range(k):
x, y = map(int, input().split())
graph[y][x] = 1
for j in range(n):
for p in range(m):
if dfs(j, p) == True:
count += 1
print(count)
Reference
'알고리즘 연습 > 백준' 카테고리의 다른 글
[Baekjoon] 10월 - 1일 1문제 풀기 기록장 (0) | 2024.10.15 |
---|---|
[Python - 1926] 그림 (S1) (0) | 2024.06.28 |
[Python - 1051] 숫자 정사각형 (S3) (0) | 2024.06.17 |
[Python - 1049] 기타줄 (S4) (0) | 2024.06.13 |
[Python - 1026] 보물 (S4) (0) | 2024.06.13 |