[백준/Python] 1987 - 알파벳

문제

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

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

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

입력

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

출력

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

풀이
언제 시도했던 문제인지는 모르겠지만 실패한 문제로 남아있길래 다시 풀어보니 아주 간단하게 해결됐다
당시에 통과를 못한 이유는 시간초과때문이었는데 지나온 알파벳을 체크하는 방법을 set을 사용해서 in으로 체크했기 때문이었다
in은 특히나 $O(n)$의 시간복잡도를 갖는 연산이기 때문에 시간초과가 발생하기 쉽다
더군다나 이 문제에서 dfs가 사방으로 갈 수 있는 곳이 없는게 아니라면 종료 조건이 없기 때문에 재귀의 깊이가 깊어질 수 있어 더더욱 시간 효율을 고려해야한다

따라서 알파벳 개수인 26만큼 26개의 False값을 갖는 리스트를 선언하고 아스키 코드를 떠올렸다
아스키 코드로 A는 65번이기 때문에 ord(현재 위치의 알파벳)-65를 계산한 값이 방문여부 리스트에서 해당 알파벳의 위치이다

예를 들어 C는 아스키코드로 67번이기 때문에 65를 뺀 2번 인덱스가 C의 방문 여부를 체크할 수 있는 위치이다

이렇게 방문 처리를 해주면 $O(1)$시간으로 방문 체크를 할 수 있기 때문에 효율적이다

이 외에는 간단한 백트래킹만 해주면 된다

import sys

r,c = map(int, sys.stdin.readline().split())
grid = []

for _ in range(r):
    grid.append(list(sys.stdin.readline().strip()))


dxs = [-1,1,0,0]
dys = [0,0,-1,1]

check = [False]*26

ans = 0

def dfs(grid, x, y, cnt):
    global ans
    ans = max(ans, cnt)
    for dx, dy in zip(dxs, dys):
        nx, ny = dx+x, dy+y
        if -1<nx<r and -1<ny<c and not check[ord(grid[nx][ny])-65]:
            check[ord(grid[nx][ny])-65] = True
            dfs(grid, nx, ny, cnt+1)
            check[ord(grid[nx][ny])-65] = False

check[ord(grid[0][0])-65] = True
dfs(grid, 0, 0, 1)
print(ans)