백준 1987: 알파벳 (Python)

문제

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

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

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

해설  

흔한 유형의 그래프 문제로, 이미 방문한 알파벳을 지나지 않으면서 갈 수 있는 최장거리를 구하는 것이 목표다.

 

예를 들어, 예제 입력 3의 경우는 다음 그림과 같이 10칸을 이동할 수 있다.

R, C의 범위가 1~20이기 때문에 이 정도 범위라면 백트래킹을 활용해 모든 경로의 수를 계산하여 답을 구할 수 있다.

 

다만 주의할점은 무지성으로 2차원 배열 visited 변수, 알파벳 딕셔너리를 둘 다 만들어 푼다면 시간초과가 나올 수 있다. "같은 알파벳이 적힌 칸을 두 번 지날 수 없다" 는 문제조건이 있음에 주목하자. 알파벳이 쓰였는지 아닌지 체크만 제대로 한다면, 각 칸에 대한 방문 여부는 따로 저장할 필요가 없다.

 

따라서 A~Z까지 26 크기의 리스트를 만든 다음, 각 알파벳 방문 여부를 True, False로 저장해 풀면 된다.

코드

result = 1


def Backtracking(x, y, board, alphabets, depth):
    # 상하좌우
    dy = [1, -1, 0, 0]
    dx = [0, 0, -1, 1]

    isNoWaytoOut = True
    for i in range(4):
        ty = dy[i] + y
        tx = dx[i] + x

        if tx < 0 or ty < 0 or tx >= C or ty >= R:  # 보드 밖으로 못나가게
            continue

        alphabet = ord(board[ty][tx])-65
        # 방문하지 않은 알파벳이 있는 칸이면
        if not alphabets[alphabet]:
            isNoWaytoOut = False
            alphabets[alphabet] = True
            Backtracking(tx, ty, board, alphabets, depth+1)

            alphabets[alphabet] = False

    if isNoWaytoOut:  # 막다른 길이면
        global result
        if result < depth:
            result = depth


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

board = [[None]*C for _ in range(R)]

for i in range(R):
    board[i] = list(input())

alphabets = [None]*100
for i in range(26):  # A~Z 리스트 생성
    alphabets[i] = False


# 1행1열 방문처리
alphabets[ord(board[0][0])-65] = True

Backtracking(0, 0, board, alphabets, 1)

print(result)