알파벳

풀이

 처음 (0, 0)부터 시작해서 조건에 맞게 경로를 탐색하면서 말이 지나갈 수 있는 최대의 칸 수를 구하는 문제다. 나는 DFS 백트래킹으로 문제를 풀었는데 python3 기준으로 시간초과 판정이 떴다. 일단 pypy로 돌려서 제출은 성공했는데 후에 python3로도 성공하도록 최적화를 할 예정이다.

R, C = map(int, input().split())
visited = [0] * 26
graph = []
for _ in range(R):
    graph.append(list(input()))

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
max_value = 0
visited[ord(graph[0][0])-65] = 1
def dfs(x,y,c):
    global max_value
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        if 0<=nx<R and 0<=ny<C:
            if visited[ord(graph[nx][ny])-65] == 0:
                visited[ord(graph[nx][ny])-65] = 1
                dfs(nx,ny,c+1)
                visited[ord(graph[nx][ny])-65] = 0
    max_value = max(max_value, c)

dfs(0,0,1)
print(max_value)

참고 : https://leeingyun96.tistory.com/22