1987번: 알파벳 (백트래킹)

www.acmicpc.net/problem/1987

1987번: 알파벳

# 알파벳
# https://www.acmicpc.net/problem/1987 (백트래킹)

# 방문경로가 다르면 재방문 가능하므로 방문리스트가 아니라 SET을 이용한다.


def dfs(x, y, step):
    global result

    # if not visited[x][y]:
    #     visited[x][y] = 1
    if (x, y, step) not in queue:
        queue.add((x, y, step))

        result = max(result, len(step))

        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < R and 0 <= ny < C and MP[nx][ny] not in step:  # 가지치기 (이전 이동경로 제외)
                dfs(nx, ny, step + MP[nx][ny])


R, C = map(int, input().split())
MP = [input() for _ in range(R)]

# visited = [[0] * C for _ in range(R)]
queue = set()

result = 0
dfs(0, 0, MP[0][0])
print(result)