백준 1987 파이썬 - 알파벳

https://www.acmicpc.net/problem/1987

1987번: 알파벳

문제

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

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

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

코드

import sys
r, c = map(int, sys.stdin.readline().split())
arr = [list(map(lambda x : ord(x) - 65, sys.stdin.readline().rstrip())) for _ in range(r)]
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
answer = 1
array = [0] * 26
array[arr[0][0]] = 1
def search(i, j, count):
    global answer
    answer = max(count, answer)
    for k in range(4):
        nx = i + dx[k]
        ny = j + dy[k]
        if 0 <= nx < r and 0 <= ny < c and array[arr[nx][ny]] == 0:
            array[arr[nx][ny]] = 1
            search(nx, ny, count + 1)
            array[arr[nx][ny]] = 0
search(0, 0, 1)
print(answer)

풀이

pypy로 제출했다. 입력 받을 때 lambda로 모두 ord(x) - 65를 해주어 문자열이 아닌 아스키 코드의 숫자로 연산을 수행해야 시간 초과가 안뜨는 것 같다. array의 26은 알파벳의 갯수이다. 해당 알파벳을 거쳤는지를 array에 1로 표시하면서 모두 탐색하고, 가장 큰 값을 answer에 저장해 최종적으로 answer를 출력하면 된다.