[백준1987번] 알파벳 / Python3

문제

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

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

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

입력

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

출력

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

예제 입력 1

2 4
CAAB
ADCB

예제 출력 1

3

나의 풀이

이 문제는 DFS를 사용하여 풀면된다. 상하좌우의 알파벳들을 확인하면서 현재까지 알파벳을 사용한 적이 없다면 사용한 것을 표시하고 재귀를 돌리고 이후 알파벳을 다시 사용 안한 것으로 되돌려주어 백트래킹을 하면 된다.

필자는 분명히 로직이 맞는데 계속 시간초과가 발생했다. 문제는 사용한 알파벳들을 배열에 담아서 배열에 있는지 없는지를 확인하고 사용하지 않은 알파벳이라면 append()를 사용하여 넣고 백트래킹을 할때에는 pop()을 사용하여 구현하였었다. BFS 문제들을 풀때에 list의 pop()과 append()는 성능이 deque보다 안 좋다는 것이 생각나서 알파벳을 list에 넣는 방법이 아닌 알파벳 26개 각각의 사용여부를 저장하는 배열을 만든 뒤에 문제를 해결하였다. 여기서 ord()를 사용하였는데 이는 문자를 아스키 코드로 변환해주는 함수이다. 파이썬은 C 같은 언어와 다르게 문자를 바로 형변환을 통해 아스키 코드로 바꿀 수 없기때문에 이와 같은 함수를 사용해야한다.

코드

# 1987번 알파벳
import sys

# dfs
def dfs(x, y, al, count):
    global board, R, C, maxCount

    # 최대 칸수 최신화
    maxCount = max(maxCount,count)

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

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

        # ord()를 사용해서 아스키 코드로 변환
        if 0 <= nx < C and 0 <= ny < R:
            c = ord(board[ny][nx]) - 65
            if not al[c]:
                al[c] = True
                dfs(nx,ny,al,count+1)
                al[c] = False

# main
R, C = map(int, input().split())

board = []
for _ in range(R):
    board.append(sys.stdin.readline())

alpha = [False] * 26    # 알파벳 방문 여부
alpha[ord(board[0][0])-65] = True

maxCount = 0    # 최대 이동 칸수
dfs(0,0,alpha,1)
print(maxCount)