알파벳

문제

세로 R칸, 가로 C칸으로된 표 모양의 보드가 있습니다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀있고, 좌측 상단 (1행 1열)에는 말이 놓여 있습니다. 말은 상하좌우로 인접한 빈칸중의 한칸으로 이동할 수 있는데 새로 이동하는 칸에 적힌 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 합니다. 즉 같은 알파벳은 두번 지날 수 없습니다. 가장 길게 이동할수있는 경로의 길이를 구하는 문제입니다.

풀이

함수를 정의합니다, dfs(좌표) : 주어진 좌표에서 시작해서 가장 길게 이동할수있는 경로의 길이.

주어진 함수는 다음과 같이 쪼개질수있습니다.

단 상/하/좌/우 재귀를 호출하기 위해서는 상/하/좌/우에 해당하는 알파벳이 현재까지 이동한 경로에 존재해서는 안됩니다.(문제 정의)
상/하/좌/우 좌표가 만약에 현재까지 이동한 경로에 존재하지 않을 경우 해당 방향에 대해서 재귀함수를 만들수있습니다.
현재 칸(1) + dfs(경로에 존재하지 않는 상/하/좌/우)

상/하/좌/우가 모두 안되는 경우도 존재합니다. 이 경우 총 이동경로가 1이 되므로(현재 칸만 포함) 1을 반환합니다.

코드

'''
Created by jun on 21/05/27
'''
R, C = map(int, input().split())
board = [list(input())for _ in range(R)]
path = set()

#y,x좌표에서 중복없이 갈수있는 최대의 수.
def dfs(y, x):
    res = 1
    path.add(board[y][x])
    for dy, dx in (-1,0), (1,0), (0,-1), (0,1):
        ny = y + dy
        nx = x + dx
        if 0 <= ny < R and 0 <= nx < C and board[ny][nx] not in path:
            res = max(res, 1 + dfs(ny, nx))
    path.remove(board[y][x])
    return res

print(dfs(0, 0))

새로 알게된 사실