Baekjoon-1743-음식물 피하기
26 Sep 2022Python의 최대 recursion depth는 100으로 설정되어 있다.
강제로 limit을 올려주면 해결 가능하다. (DFS에서 자주 발생 할 듯!!)
그러나 1e6 이상으로는 올릴 수 없으니 너무 큰 그래프에서 탐색을 시행할 땐 BFS를 사용할 것
import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline
N,M,K = map(int, input().split())
maps = [[0 for _ in range(M)] for _ in range(N)]
for _ in range(K):
r,c = map(int, input().split())
maps[r-1][c-1] = 1
visited = [[0 for _ in range(M)] for _ in range(N)]
def dfs(i,j,maps):
global visited, N, M
result = 1
visited[i][j] = 1
for u,v in [(i-1,j), (i+1,j), (i,j-1), (i,j+1)]:
if u >= 0 and u < N and v >= 0 and v < M:
if visited[u][v] == 0 and maps[u][v] == 1:
result += dfs(u,v,maps)
return result
max_size = 0
for n in range(N):
for m in range(M):
if visited[n][m] == 0 and maps[n][m] == 1:
max_size = max(max_size, dfs(n,m,maps))
print(max_size)