BOJ 1743 음식물 피하기

백준 1743 링크

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

문제풀이

파이썬으로 dfs등의 재귀함수를 이용할때 주의해야 할 점은 파이썬은 재귀를 1000번 까지만 허용합니다.

 

그래서 이 문제같이 최대 100*100 = 10000번을 재귀로 돌아서 1000번 이상 재귀를 돌 경우에선

import sys
sys.setrecursionlimit(100000)

를 입력해주어 재귀의 제한을 풀어줘야 합니다. 코드에선 10만번정도로 제한을 늘려놓았습니다.

 

이걸 몰라서 런타임에러를 계속 두드려맞았네요.

코드

import sys
sys.setrecursionlimit(100000)
def dfs(y,x,result):
    result=result+1
    M[y][x]=0
    for _ in range(0,4):
        ny,nx = y+ly[_], x+lx[_]
        if 1<=ny<=n and 1<=nx<=m and M[ny][nx]==1:
           result = result + dfs(ny,nx,0)
    return result
lx=[1,-1,0,0];ly=[0,0,1,-1]
n,m,k = map(int, input().split())
M = [[0]*(m+3) for _ in range(n+3)]
for _ in range(k):
    y,x=map(int, input().split())
    M[y][x]=1
ans=0
for i in range(1,n+1):
    for j in range(1,m+1):
        if M[i][j]==1:
            ans=max(ans,dfs(i,j,0))
print(ans)