[백준] 1987 - 알파벳 (Python)

문제

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

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

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

입력

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

출력

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

 

 

 

---

풀이

DFS와 백트래킹 알고리즘을 사용했다.

 

처음에 BFS로 시도하였다가 메모리 오류가 났고 DFS로 시도했더니 시간 초과가 났다.

 

처음에는 방문한 알파벳을 집합에 저장하였는데

알파벳은 26자밖에 되지 않으니 알파벳을 인덱스로 변환하여 boolean으로 변경하니 풀렸다.

 

import sys

input = sys.stdin.readline

R, C = map(int, input().split())
graph = []
for i in range(R):
    li = list(map(str, input().strip()))
    graph.append(li)

def dfs(x, y, visited):
    direction = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    max_path = 0

    for dx, dy in direction:
        nx, ny = x + dx, y + dy
        if 0 <= nx < R and 0 <= ny < C:
            char_index = ord(graph[nx][ny]) - ord('A')
            if not visited[char_index]:
                visited[char_index] = True
                max_path = max(max_path, dfs(nx, ny, visited) + 1)
                visited[char_index] = False

    return max_path

visited = [False] * 26
visited[ord(graph[0][0]) - ord('A')] = True
print(dfs(0, 0, visited) + 1)