파이썬 알고리즘 144번 | [백준 1012번] 유기농 배추 - dfs

144. 유기농 배추

1) 어떤 전략(알고리즘)으로 해결?

• 자신과 붙어있는 덩어리들을 찾기 위해서 dfs로 한번 들어가면 깊이로 탐색

2) 코딩 설명

<내 풀이>

import sys
sys.setrecursionlimit(10**6)#런타임에러방지용

t=int(sys.stdin.readline())

# mapp
global mapp
mapp=[]

def chk(x,y):
    if x<0 or y<0 or x>=m or y>=n: # 탐색하다가 범위 벗어났다면 
        return
    if mapp[x][y]==0 : #배추 이미 찾았거나, 아까 찾은 배추
        return
    # 배추가 존재하면 그 배추 부분은 
    #상하좌우 다시 체크 진행하기
    mapp[x][y]=0

    chk(x-1,y)
    chk(x,y-1)
    chk(x,y+1)
    chk(x+1,y)

    
worm=0

for i in range(t):
    worm=0
    mapp=[]
    m,n,k=map(int,sys.stdin.readline().split())
    for j in range(m):
        mapp.append([0]*n) #모두 0으로 초기화 n * m 만큼

    for z in range(k): #배추 있는데 표시해
        x,y=map(int,sys.stdin.readline().split())
        mapp[x][y]=1
        
        # for i in mapp:
        #     print(i) #mapp 출력 확인

    for r in range(m) : #세로 만큼 (행의 길이 만큼)
        for c in range(n) : #열을 돈다
            if mapp[r][c]==1:
                chk(r,c)
                worm+=1
    print(worm)

<다른 분의 풀이 or 내 틀렸던 풀이, 문제점>

출처 : 출처

import sys
t=int(sys.stdin.readline())

# mapp
global mapp
mapp=[]

def chk(x,y):
    if x<0 or y<0 or x>=m or y>=n: # 탐색하다가 범위 벗어났다면 
        return
    if mapp[x][y]==0 : #배추 이미 찾았거나, 아까 찾은 배추
        return
    # 배추가 존재하면 그 배추 부분은 
    #상하좌우 다시 체크 진행하기
    mapp[x][y]=0

    chk(x-1,y)
    chk(x,y-1)
    chk(x,y+1)
    chk(x+1,y)

    
worm=0

for i in range(t):
    worm=0
    mapp=[]
    m,n,k=map(int,sys.stdin.readline().split())
    for j in range(m):
        mapp.append([0]*n) #모두 0으로 초기화 n * m 만큼

    for z in range(k): #배추 있는데 표시해
        x,y=map(int,sys.stdin.readline().split())
        mapp[x][y]=1
        
        # for i in mapp:
        #     print(i) #mapp 출력 확인

    for r in range(m) : #세로 만큼 (행의 길이 만큼)
        for c in range(n) : #열을 돈다
            if mapp[r][c]==1:
                chk(r,c)
                worm+=1
    print(worm)

=> Runtime Error : https://help.acmicpc.net/judge/rte/RecursionError

• RecursionError는 재귀와 관련된 에러입니다. 가장 많이 발생하는 이유는 Python이 정한 최대 재귀 깊이보다 재귀의 깊이가 더 깊어질 때입니다.
• Python이 정한 최대 재귀 깊이는 sys.getrecursionlimit()을 이용해 확인할 수 있습니다. BOJ의 채점 서버에서 이 값은 1,000으로 되어 있습니다.

해결책 :

• sys.setrecursionlimit()을 사용하는 것입니다. 이 함수를 사용하면, Python이 정한 최대 재귀 갚이를 변경할 수 있습니다. 소스 1의 최대 재귀 깊이를 1,000,000 정도로 크게 설정하면 런타임 에러 없이 실행이 됩니다.

=> 코드에

import sys
sys.setrecursionlimit(10**6)#런타임에러방지용

추가하면 완료!

<반성 점>

• dfs, bfs는 재귀적으로 호출하고 return하는 작업을 반복해야하므로, 따로 함수를 빼준 후 적절한 조건에서 return 해주도록 코드를 작성해야 하는 과정을 거쳐야 한다.

<배운 점>