백준 1987번: 알파벳(Python, DFS응용, 백트래킹)

문제

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

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

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

입력

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

출력

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

import sys

R, C = map(int,sys.stdin.readline().split())

boards = []

for _ in range(R):
    string = str(sys.stdin.readline().strip())
    boards.append(string)

def is_valid(nx, ny):
    if 0<= nx < R and 0<= ny < C:
        return True
    return False

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

queue = []
used_alphabets = set()
answer = 1

def dfs(x, y, count):
    global answer
    
    if count > answer:
        answer = count
        if answer == 26:
            print(26)
            exit()
    
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if is_valid(nx,ny):
            if boards[nx][ny] not in used_alphabets:
                used_alphabets.add(boards[nx][ny])
                dfs(nx,ny, count + 1)
                used_alphabets.remove(boards[nx][ny])

used_alphabets.add(boards[0][0])
dfs(0,0,1)
print(answer)