백준 1987 알파벳

문제

• 0, 0 에 말이 놓여 있음
• 지금까지 지난 알파벳이 아니어야 이동할 수 있음
• 최대 몇 칸을 지날 수 있는지

과정

• DFS를 사용하고자 했다.
• 지나간 알파벳을 기억해야하서 백트래킹을 사용했다.
• 최대 길이를 구해야했기에 전역 변수를 사용했다.

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

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

map_lst = [list(input()) for _ in range(R)]
visited = [[False for _ in range(C)] for _ in range(R)]

visited_word = [False] * 26

ans = 0


def dfs(x, y, cnt):
    global ans
    ans = max(cnt, ans)
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or nx >= C or ny < 0 or ny >= R or visited[ny][nx] or visited_word[ord(map_lst[ny][nx]) - 65]:
            continue
        visited_word[ord(map_lst[ny][nx]) - 65] = True
        dfs(nx, ny, cnt + 1)
        visited_word[ord(map_lst[ny][nx]) - 65] = False


visited_word[ord(map_lst[0][0]) - 65] = True
dfs(0, 0, 1)
print(ans)

• 원래 지난 알파벳을 기억하는 용도로 딕셔너리를 썼었다.
• 딕셔너리를 사용하면 시간초과가 발생하고, 리스트를 사용하니 시간초과가 발생하지 않았다.
• 파이썬의 딕셔너리는 트리를 기반으로 만들어져서 인덱스 접근이 느리다.
• 딕셔너리는 값의 범위가 매우 큰 경우에 데이터를 빠르게 삽입, 삭제할 수 있다는 점이다.
• 이 문제에서는 알파벳 수가 26가지 뿐이므로 리스트가 효율적이다.