[백준 / Python] 1012번 유기농 배추 | 초코더

https://www.acmicpc.net/problem/1012

1012번: 유기농 배추

접근법

1. dfs()함수

아래의 게시글을 참고하시면 DFS함수부분은 모두 동일합니다!

https://sinsomi.tistory.com/entry/%EB%B0%B1%EC%A4%80-Python-2667%EB%B2%88-%EB%8B%A8%EC%A7%80%EB%B2%88%ED%98%B8%EB%B6%99%EC%9D%B4%EA%B8%B0-%EC%B4%88%EC%BD%94%EB%8D%94

[백준 / Python] 2667번 단지번호붙이기 | 초코더

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()