[BackTracking] Python - 1987번, 알파벳

def dfs(x, y, cntMove):
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]

    global RET
    RET = max(RET, cntMove)

    for i in range(4):
        curX = x + dx[i]
        curY = y + dy[i]

        if (0 <= curX <= R-1) and (0 <= curY <= C-1):
            if(isVisitedAlphabet[getNumberOfAlphabet(board[curX][curY])] == False):
                isVisitedAlphabet[getNumberOfAlphabet(
                    board[curX][curY])] = True
                dfs(curX, curY, cntMove+1)
                isVisitedAlphabet[getNumberOfAlphabet(
                    board[curX][curY])] = False

def getNumberOfAlphabet(char):
    return ord(char)-ord('A')

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

isVisitedAlphabet = [False]*26
isVisitedAlphabet[getNumberOfAlphabet(board[0][0])] = True
RET = 1

dfs(0, 0, RET)
print(RET)

dfs를 해준 후, isVisitedAlphabet를 다시 False로 맞춰주는 것이 핵심입니다.

또한, 지나온 길을 따로 저장하지 않아도 되는 이유는, 이미 지나온 길은 알파벳이 중복되기 때문입니다.

 

 

Python은 시간초과여서 PyPy3으로 겨우 통과했습니다. 숨이 턱턱 막히네요.