[Python] 1987 - 알파벳

문제

세로 R$R$칸, 가로 C$C$칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1$1$행 1$1$열) 에는 말이 놓여 있다.

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

입력

첫째 줄에 R$R$과 C$C$가 빈칸을 사이에 두고 주어진다. (1≤R,C≤20$1 ≤ R,C ≤ 20$) 둘째 줄부터 R$R$개의 줄에 걸쳐서 보드에 적혀 있는 C$C$개의 대문자 알파벳들이 빈칸 없이 주어진다.

출력

첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.

해설

2번 시도 후 맞았습니다.

1번째에서는 visited를 리스트로 관리해서 시간이 많이 걸렸어서 시간 초과 뜬 것 같고 이후 딕셔너리로 바꾸어 정답 인정됨.

소스 코드

r, c = map(int, input().split())  
board = \[list(input()) for \_ in range(r)\]  

dx = \[-1, 1, 0, 0\]  
dy = \[0, 0, -1, 1\]  
answer = 0  

visited = {chr(ord('A') + i): False for i in range(26)}  

def dfs(x, y, count):  
    global answer  
    answer = max(answer, count)  
    for i in range(4):  
        nx, ny = x + dx\[i\], y + dy\[i\]  
        if 0 <= nx < r and 0 <= ny < c:  
            char = board\[nx\]\[ny\]  
            if not visited\[char\]:  
                visited\[char\] = True  
                dfs(nx, ny, count + 1)  
                visited\[char\] = False  # 백트래킹  

# 시작 위치 방문 표시  
visited\[board\[0\]\[0\]\] = True  
dfs(0, 0, 1)  

print(answer)