[백준-파이썬] 1012번: 유기농 배추

백준 1012번 문제 보러가기~~

📌 포인트

DFS로 풀었다!!
방금 푼 단지번호 붙이기 문제와 비슷한 것 같다.
백준 단지번호 붙이기 문제 보러가기
내 풀이 보러가기

😅 위기

잘 풀었다고 생각했는데 '런타임 에러 (RecursionError)'가 나왔다.
DFS로 풀었는데 다음에는 BFS로 생각해봐야지~
백준 안내에 있는 대로

import sys
sys.setrecursionlimit(10**6)

를 추가해서 파이썬 최대 재귀 깊이를 크게 설정하니 성공했다.

👩‍💻 코드와 설명

import sys
sys.setrecursionlimit(10**6) # 최대 재귀 깊이 설정

dx=[-1,0,1,0]
dy=[0,1,0,-1]

def DFS(x,y):
    for p in range(4): #상하좌우 배추가 있는지 체크
        xx = x + dx[p]
        yy = y + dy[p]

        if 0 <= xx < n and 0 <= yy < m and board[xx][yy] == 1: #범위를 만족하고, 배추가 있으면
            board[xx][yy] = 0 #그 부분 다시 가지 않도록 0으로 바꾸기
            DFS(xx, yy)


if __name__=='__main__':
    t=int(input())
    for _ in range(t):
        m,n,k=map(int,input().split())
        board=[[0]*m for _ in range(n)] #밭 전체를 0으로

           #배추가 있는 위치를 가져와서, 1로 체크하기
        for _ in range(k):
            x,y=map(int,input().split())
            board[y][x]=1

        '''for x in board:
            print(x)'''

        cnt=0
        for i in range(n):
            for j in range(m):
                if board[i][j] == 1: #쭉~~ 살펴보다가 배추가 있으면
                    cnt+=1     #배추 수 더해주기
                    board[i][j] = 0 #그 부분 다시 가지 않도록 0으로 바꾸기
                    DFS(i, j)
        print(cnt)