[백준 / Python] 1012번 유기농 배추 | 초코더
https://www.acmicpc.net/problem/1012
1012번: 유기농 배추
차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. (
www.acmicpc.net
접근법
1. dfs()함수
아래의 게시글을 참고하시면 DFS함수부분은 모두 동일합니다!
[백준 / Python] 2667번 단지번호붙이기 | 초코더
https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 <그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인..
sinsomi.tistory.com
2. solve()함수
solve() 함수도 위의 게시글과 동일한데 다른점은, 위의 게시글은 단지수와 각 단지의 집의 수를 출력하는
것이고, 여기서는 지렁이의 개수만 구하면 되므로, dfs()함수를 실행하는 횟수만 구해주면 됩니다!
3. 함수 실행부분
총 테스트 케이스를 t로 받아온후, 전체 과정을 t번 반복해줍니다.
m,n,k를 입력받아오고 matrix의 값을 설정해줍니다.
나의 풀이
import sys
sys.setrecursionlimit(50000) #재귀제한높이설정(기본값이상으로 안해주면 런타임에러) ※기본값:1000
dx=[-1,0,1,0]
dy=[0,1,0,-1]
cnt=0
land=[]
def dfs(x,y):
matrix[x][y]= 0
for i in range(4):
nx=x+dx[i]
ny=y+dy[i]
if nx<0 or nx>=m or ny<0 or ny>=n:
continue
if matrix[nx][ny] == 1:
dfs(nx,ny)
def solve():
cnt=0
for i in range(m):
for j in range(n):
if matrix[i][j] == 1:
dfs(i,j)
cnt+=1
print(cnt)
t=int(input())
for _ in range(t):
m,n,k = list(map(int,sys.stdin.readline().split()))
matrix=[[0]*n for _ in range(m)]
for _ in range(k):
link=list(map(int,input().split()))
matrix[link[0]][link[1]]=1
solve()