Jae-Kyung Cho LLM Developers who was a Robotics engineer

Baekjoon-1743-음식물 피하기

Python의 최대 recursion depth는 100으로 설정되어 있다.
강제로 limit을 올려주면 해결 가능하다. (DFS에서 자주 발생 할 듯!!)
그러나 1e6 이상으로는 올릴 수 없으니 너무 큰 그래프에서 탐색을 시행할 땐 BFS를 사용할 것

ref: https://velog.io/@jwun95/DFS-%EB%B0%B1%EC%A4%80-1743%EB%B2%88-%EC%9D%8C%EC%8B%9D%EB%AC%BC-%ED%94%BC%ED%95%98%EA%B8%B0

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)
Comments