백준 1987 : 알파벳 (Python)

백준 1987 문제

문제

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

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

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

입력

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

출력

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

예제 입력 1

2 4
CAAB
ADCB

예제 출력 1

3

---

나의 풀이

• 방문 가능한 경로를 트리로 구조화할 수 있고 방문한 알파벳을 기억해야 하기에 전형적인 백트래킹 문제이다. 나는 DFS로 백트래킹을 구현했는데 처음에 제출했을 때에는 시간초과가 발생했다. 처음에는 방문한 알파벳을 seq 리스트로 관리해 DFS 수행할 때마다 리스트를 순회해 시간복잡도가 컸다. 이를 절감하기 위해 alpha 리스트에 방문 여부를 기록하도록 구현했다. 이렇게 구현하면 방문 여부 확인에 O(1)이 걸리기에 시간 복잡도를 줄일 수 있다. 이렇게 코드를 바꿨음에도 Python3로 컴파일하니 시간초과가 발생해 PyPy3로 제출해보았다. 그 결과... 어찌저찌 통과를 하기는 했다.. 제출한 코드는 아래와 같다.

import sys 

answer = 0 

R,C = map(int,sys.stdin.readline().split())
board = [list(map(str,sys.stdin.readline().strip())) for _ in range(R)]
board = [[(ord("A")-ord(board[i][j])) for j in range(C)] for i in range(R)]
alpha = [False for _ in range(26)]

def DFS(r,c,cnt):
    global R,C,board,answer
    
    dr = [1,-1,0,0]
    dc = [0,0,1,-1]
    
    answer = max(answer,cnt)
    
    for i in range(4):
        nr,nc = r+dr[i],c+dc[i]
        if (0<=nr<R and 0<=nc<C):
            if alpha[board[nr][nc]]==False:
                alpha[board[nr][nc]] = True 
                DFS(nr,nc,cnt+1)
                alpha[board[nr][nc]] = False  

alpha[board[0][0]] = True 
DFS(0,0,1)
print(answer)

• DFS보다 BFS가 통상 빠르게 동작한다고 알려져있고 이 문제에서 트리 깊이가 무한대로 발생할 수 있는 것도 아니니 BFS로 구현하면 시간복잡도를 조금 줄일 수 있지 않을까 싶기도..