소스코드

import sys
input = sys.stdin.readline

R, C = map(int, input().strip().split())
board = []
drow = [-1, 1, 0, 0]
dcol = [0, 0, -1, 1]

for _ in range(R):
    board.append(list(input().strip()))

# 현재 좌표 기준 인접 좌표들 DFS 탐색 후, 인접 탐색 결과값들과 내 위치까지의
# 결과값 중 최대값을 리턴
def DFS(cur_r, cur_c):
    result = len(path)

    for i in range(4):
        adj_r = cur_r + drow[i]
        adj_c = cur_c + dcol[i]

        if not (0 <= adj_r < R and 0 <= adj_c < C):
            continue
        
        if board[adj_r][adj_c] in path:
            continue

        path.add(board[adj_r][adj_c])
        result = max(result, DFS(adj_r, adj_c))
        path.remove(board[adj_r][adj_c])

    return result

# 집합으로 path를 기록
# 경로 길이 계산과 방문 여부 체크를 set을 통해 수행 가능
path = set(board[0][0])
print(DFS(0, 0))

풀이 요약 (pypy3만 통과)

1. 전형적인 백트래킹 문제이다. 핵심 아이디어는 set의 활용이다.

   set에 경로 알파벳을 기록하면서, set의 길이를 탐색 길이로 취급하고, 방문 여부는 대상 알파벳이 set에 들어있는지 여부로 판단한다. len과 in 연산 둘 다 O(1) 이다.

2. 주의할 점은, 이 풀이는 pypy3만 통과한다. python3로는 DFS가 아닌 다른 방식을 활용해야 TLE가 안 나오는 듯하다.

   그리고 4방향 인접 좌표를 순회할 때, 제너레이터를 쓰면 pypy3로도 TLE가 난다. 아마도 drow, dcol을 선언해두는 방식보다 제너레이터 방식이 시간이 조금 더 오래 걸리는 듯 하다.

어려웠던 점, 배운 점

1. 순회 구조를 만들 때, 제너레이터 방식이 drow, dcol(또는 dx, dy) 선언&활용 방식보다 시간이 조금 더 오래 걸린다는 것을 알게 되었다. 앞으로는 후자의 방식을 주로 활용해야겠다.