Backjoon 1012번 유기농 배추

백준 알고리즘

• 1012번 유기농 배추

---

DFS를 사용하면 풀수 있는 문제입니다. 이번에는 스택이나 큐를 사용하지 않고 리스트와 리컬시브만을 사용해서 풀어봤습니다.
결국 DFS도 스택큐를 이용한 리컬시브겠죠? 1이 있는 곳에서 상하좌우를 순회하며 1을 다 0으로 바꿉니다.
그럼 sol 함수가 몇번 호출되는지 카운팅 하면 답이 됩니다.

---

정답 코드

import sys
sys.setrecursionlimit(50000)
def sol(x,y):
    mat[x][y]= 0
    for i in range(4):
        mx = dx[i]+x
        my = dy[i]+y
        if (0<=mx<n and 0<=my<m and mat[mx][my]==1):
            sol(mx,my)            
t= int(input())
dx=[0,0,1,-1]
dy=[1,-1,0,0]
for i in range(t):
    m,n,k=map(int,input().split())
    mat=[[0]*m for i in range(n)]
    for i in range(k):
        a,b = map(int,input().split())
        mat[b][a] = 1        
    ans=0
    for i in range(n):
        for j in range(m):
            if (mat[i][j]==1):
                sol(i,j)
                ans+=1
    print(ans)