이번 문제는 깊이우선탐색을 통해 쉽게 해결하였다. 통로에 1이 있을 경우 1을 0으로 바꿔주고 4가지 방향으로 탐색을 진행하며 각 탐색마다 카운팅 변수를 1 증가시키고 결과적으로 카운팅 변수를 반환하는 재귀함수를 작성하여 해결하였다.

• 재귀 제한을 늘려준다.
• dfs함수를 h, w, cnt를 인자로 갖도록 선언한다.
  -> path[h][w]를 0으로 갱신한다.
  -> 4가지 탐색 방향을 저장하는 리스트 dh, dw를 선언하고 4가지 탐색 방향을 짝지어 저장한다.
  -> 4번 반복하는 i에 대한 for문을 돌린다.
  --> nh를 h+dh[i]로 갱신한다.
  --> nw를 w+dw[i]로 갱신한다.
  --> 만약 nh, nw가 0보다 크고, nh가 n보다 작거나 같고, nw가 m보다 작거나 같고, path[nh][nw]가 1일 경우, cnt를 dfs(nh, nw, cnt+1)로 갱신한다.
  -> cnt를 반환한다.
• n, m, k를 입력받는다.
• 통로에 해당하는 리스트 path를 선언하고 0을 (n+1)*(m+1)로 채워준다.
• 결과를 저장하는 변수 answer를 0으로 선언한다.
• k번 반복하는 for문을 돌린다.
  -> r, c를 입력받는다.
  -> path[r][c]를 1로 갱신한다.
• 1부터 n까지 반복하는 i에 대한 for문을 돌린다.
  -> 1부터 m까지 반복하는 j에 대한 for문을 돌린다.
  --> 만약 path[i][j]가 1일 경우 answer를 answer과 dfs(i, j, 1) 중 더 큰 값으로 갱신한다.
• answer를 출력한다.

Code

import sys
sys.setrecursionlimit(10**9)
def dfs(h, w, cnt):
    path[h][w]=0
    dh=[0, 0, -1, 1]
    dw=[1, -1, 0, 0]
    for i in range(4):
        nh=h+dh[i]
        nw=w+dw[i]
        if nh>0 and nw>0 and nh<=n and nw<=m and path[nh][nw]==1:
            cnt=dfs(nh, nw, cnt+1)
    return cnt
n, m, k=map(int, input().split())
path=[[0]*(m+1) for _ in range(n+1)]
answer=0
for _ in range(k):
    r,c=map(int, input().split())
    path[r][c]=1
for i in range(1, n+1):
    for j in range(1, m+1):
        if path[i][j]==1:
            answer=max(answer, dfs(i, j, 1))
print(answer)